This quarter, a university will give at most ~m~ special scholarships to the best students who meet criteria: earn at least ~k~ credits (each passed courses is ~4~ credits), and GPA equals or greater ~p~. Output the list of students gets the scholarship.

Input

• The first line contains ~4~ integer ~n, m, k, p~ ~(n ≤ 10^5)~ which are the number of students, the number of scholarships, the minimum number of credits and the required GPA.
• In the next ~n~ lines, each represents a student:
  • Student's name (including lower case letters and not exceeding ~20~ characters).
  • ~c~ - the number of courses that the student took ~(1 ≤ c ≤ 30)~
  • ~c~ integers which are scores of ~c~ courses ~(c_i ≤ 100)~

Output

• The list of students sorted in the decreasing order of average score and increasing name. If two students have the same average scores should both receive scholarships, or none of them receive scholarship.

Example Input:

6 3 8 75 
nam 2 80 90
an 2 90 90
ngoc 2 100 40
duc 1 100
khanh 2 100 90
phi 2 90 80

Example Output:

khanh 95
an 90

Note

• The answer has an error margin between the results of no more than ~10^{-4}~.