Time Limit: 10 sec
Memory Limit: 32 MB
LAMAbpo is a Lithuanian organization which decides whether to admit the student to university or not. In this task your are required to write an application for a part of the LAMAbpo system. Given the score for each of the study programmes included in the application of high-school graduates you have to find the results of the admissions.
Essentially, the application includes: the list of study programmes ordered by priority from highest to lowest (application entry) and the personal data of a graduate. The contest is performed as indicated in the rules below:
Be aware, that if you mark an entry as considered you must be sure that either a contestant may not be accepted to the study programme or he must be accepted to this study programme.
You are given a single test. The test starts with a number of study programmes S
and a number of high-school graduates M
. S
and M
are separated by a single space. Then a list of study programmes follows. Each study programme description consists of 2 lines:
I
(1 ≤ I ≤ 1000) and a number of students to admit study programme A
(0 ≤ A ≤ 35000), respectively.
There may not be 2 programmes with the same identification code in the
input file and total number of entries of all study programmes will not exceed E
(E ≤ 200000).
The description of the study programmes is followed by M
applications. Each application consits of the following lines:
L
indicated in the application by the graduate and a unique positive integer U
(U ≤ 109) given to a contestant (which is considered if 2 contestants have the same score) separated by a space.
L
(L ≤ 16) lines containing the identification code of a study programme and the contestant score G
(G ≤ 10000) with at most 2 digits after decimal point. The numbers are separated by a single space. Score may not be negative. The study programme may not appear in the same application more than once. There will be no identification code with the study programme that does not exist.
You have to output a list of study programmes in order as they appear in the input file with the following information:
U
should be first. Each name is preceded by a number indicating a place of the graduate in the list and a space character (refer sample output).
2 4 Informatika 620 2 Matematika 621 1 Simas Simaitis 2 9529032 620 10.5 621 10.0 Jonas Jonaitis 1 3984329 621 11.5 Erika Erikaite 2 2499345 621 11.5 620 11.5 Vaclovas Vaclovaitis 2 1451044 621 9.5 620 20.5
Informatika 2 1. Vaclovas Vaclovaitis 2. Erika Erikaite Matematika 1 1. Jonas Jonaitis