EIU Programming Practices and Exams

Mr Q was tasked to write a payroll Software. The company requires employees to work k days within a month. The salary of an employee is calculated as follows:

d/ k x s where 

• d is the number of days the employees go to work
• k is the required number of days
• s is the maximum salary 

If employees work less than 4 hours, it is not counted as a working days and less than 8 hours, it is only calculated as 0.5 days. Mr. Q has received the report on working time and salary of the employee, please help him to calculate the salary for the employee.

Note that this company does not distinguish between weekends and holidays, and there is no allowance for work beyond the prescribed number of days.

Input

The first line contains 3 positive integers, the number of employees n, the minimum number of working days k, and the number of days m the company works in the month. ( n ≤ 10⁵, k ≤ m ≤ 23)

In the next n lines, each line represents an employee, including:

• Employee Id c (an integer which contains no more than 7 digits)
• Name (contains no more than 20 lower letter characters).
• The maximum salary ( 1000 ≤ l ≤ 10⁸).
• m integers which are the number of hours he/she works in m days..

Output

Export payroll of employees, each employee includes employee id, employee name is the salary received. The list is sorted by ascending name, employee id increases and salaries are rounded to the unit

Example

Input:
5 5 7
10001 phuc 1000000 8 8 8 4 4 4 4
10002 phu 12000000 8 8 8 4 4 4 3
10032 phi 8000000 0 8 4 6 4 4 8
11232 an 8000000 8 8 8 4 8 8 8
10232 an 8000000 8 8 4 8 8 8 0

Output:
10232 an 8000000
11232 an 8000000
10032 phi 6400000
10002 phu 10800000
10001 phuc 1000000