It's unbelievable, but an exam period has started at the OhWord University. It's even more unbelievable, that Valera got all the tests before the exam period for excellent work during the term. As now he's free, he wants to earn money by solving problems for his groupmates. He's made a list of subjects that he can help with. Having spoken with n of his groupmates, Valera found out the following information about them: what subject each of them passes, time of the exam and sum of money that each person is ready to pay for Valera's help. Having this data, Valera's decided to draw up a timetable, according to which he will solve problems for his groupmates. For sure, Valera can't solve problems round the clock, that's why he's found for himself an optimum order of day and plans to stick to it during the whole exam period. Valera assigned time segments for sleep, breakfast, lunch and dinner. The rest of the time he can work. Obviously, Valera can help a student with some subject, only if this subject is on the list . It happened, that all the students, to whom Valera spoke, have different, but one-type problems, that's why Valera can solve any problem of subject list i in t i minutes. Moreover, if Valera starts working at some problem, he can break off only for sleep or meals, but he can't start a new problem, not having finished the current one. Having solved the problem, Valera can send it instantly to the corresponding student via the Internet. If this student's exam hasn't started yet, he can make a crib, use it to pass the exam successfully, and pay Valera the promised sum. Since Valera has little time, he asks you to write a program that finds the order of solving problems, which can bring Valera maximum profit. The first line contains integers m , n , k ( 1 ≤ m , n ≤ 100 , 1 ≤ k ≤ 30 ) — amount of subjects on the list , amount of Valera's potential employers and the duration of the exam period in days. The following m lines contain the names of subjects