Alan has recently joined an Engineering college. On the first day he came to know that each semester will contain N number of subjects and Di (where 1<=i<=N) is the credit associated with that particular subject. In order to be eligible for the next semester each student must get at least X number of credits from the current semester. After knowing this Alan became tensed and nervous, but after discussing with seniors he came to know that getting X number of credits from N number of subjects is easy if they concentrate on particular subjects rather than all subjects. But Alan is having preference list of subjects. As compared with others Alan will give more preference to the subjects listed in preference list.
Based on past results Alan expects pass percentage Pi (where i<=i<=N) for each subject. Now Alan needs to get X number of credits in the current semester. Can you please help the Alan to select the subjects on which he needs to concentrate on, to get exactly X number of credits.
Input Format:
First line of input contains a single integer N, number of subjects present in a current semester, next N lines follows each line contains Si, Di, Pi where Si is the name of the subject, Di is the credit associated with the particular subject, Pi is the pass percentage of the subject. After N lines next line contains X, number of credits needed and the final line will contain the Alan’s preference list (N subjects, separated by a space).
Line 1
N , where N is the Number of subjects present in a current semester
Line 2
S1 D1 P1 ,
where S1 is the name of the subject
D1 is the credit associated with the particular subject and
P1 is the pass percentage of the subject
… Si Di Pi
Line N+1
Sn Dn Pn
Line N+2
X , where X is the number of credits needed
Line N+3
S1 S2…SN , where Si is the subjects of Alan according to his preference
Constraints:
1<=N<=25, where N is the number of subjects.
1<=|Di|<=100, where |Di| is the credits associated with the subject (where 1<=i<=N).
1<=X<=C (C=Sum of Di, where i=1, …, N), where X is the credits needed for next semester’s promotion.
1<=|Si|<=50, where |Si| is the subject name length (where 1<=i<=N).
1<=Pi<=100, where Pi is the pass percentage of the subject (where 1<=i<=N).
Note:
- If there present multiple set of subjects, then print the first set with highest average pass percentage, and if there are any sets with same average pass percentage then select the set based on the preference list. Please print the subject names separated by a space.
- There will be at-least one way to get X number of credits.
Output:
Line 1
For Valid Input, print
A set of subjects among N subjects on which Alan needs to concentrate on. Output the subjects based on the preference list ordering.
Sample Input and Output
Input:
5
Maths 5 80
Physics 6 75
Chemistry 10 85
Drawing 1 70
English 4 80
11
Maths Drawing Physics English Chemistry
OUTPUT:
Maths Physics