Description

To prevent STL sort, STL below are NOT ALLOWED <algorithm>, <queue>,<map>,<set>, <list> and <forward_list>

One day a disaster occurs, and many casualties need to be sent to Panda Hospital and Bear Hospital immediately. The hospital receives the lists of casualties, and each person has a data of:

1. Name
2. Age
3. Money
4. Hospital Membership
5. Membership Join Date

Note: It is okay to have multiple people with the same data.
Membership Join Date will be“NaN” if they don’t have membership.

鄭嘉成 got internship at Panda Hospital. Given the raw data in the beginning, his task is to manage the list each M days. However he is so lazy, so he hires TA  Aurick and then since TA Aurick is also lazy then he hires you!

On day i^th there will be extra P_i patients added to the list. Then Panda Hospital can only treat the first X_i most prioritized patients with Panda Hospital priorities policies. If there are still too many patients left, the next K_i most prioritized patients will be sent to Bear hospital with the Bear hospital priorities policies. Each day you need to report all list of treated patients in Panda Hospital. Also, all treated patients should be removed from the list.

As the hospital has its limit and priorities , here are list from the highest to the lowest priority criteria in Panda Hospital:

1. People with Hospital Membership
2. Longest to shortest membership join date
3. Name in Alphabetical Order
4. The input order (patient appearing first in the input list will be treated first)

While in Bear Hospital the priorities are different from Panda Hospital, here is the priority list from the highest to the lowest priority criteria in Bear Hospital :

1. People with largest amount of money to lowest money
2. The input order (patient appearing first in the input list will be treated first)  

Note: If the current list is less than X_i you can just accept all of them to Panda Hospital, and no patient will be sent to Bear Hospital. Otherwise, the rest of the patients that Panda Hospital could not manage will be sent to another hospital with maximum of K_i patients ( Which means if the remaining less than K_i we will sent all of the patients to the Bear Hospital ) .

Each day you need to print the list of treated patients in Panda hospital and the income of Panda Hospital on that day. The income is determined by all treated patient’s money * 90%. (No need to handle floating point as the money always divisible by 10)

Input

The first line will be integer s N and M (1 <= N <= 2000 and 1 <= M <= 100 )

The next 2 * N lines will be the raw data, each 2 lines have:

• first line contains full name of the patient
• second line contains the input below, separated by spaces ：
  • age (0 <= age <= 100)
  • money (10 <= money <= 10⁶) ( guarantee multiples of 10 to avoid floating error)
  • hospital membership (1 if a member, 0 if not)
  • Membership Join Date ( Format:“YYYY-MM-DD” or it’s guarantee “NaN” if they are not member)

The next M times contain following input, from the first day until the M-th day:

• First line contains Integer P X K (0 <= P <= 1000, 0 <= (X, K) < 2³¹)
• Next 2 * P lines contain list of people who will be added to the list , each 2 lines have:
  • first line contains full name of the patient.
  • second line contains below input, separated by spaces:
    • age (0 <= age <= 100)
    • money (10 <= money <= 10⁶) (guarantee multiples of 10)
    • hospital membership (1 if a member, 0 if not)
    • Membership Join Date (Format: YYYY-MM-DD and could be “NaN”)

The total number of patients in 1 day will not exceed 100000.

For testcase 1-3:    (0 <= N <= 100), (total lists per day/2 <= X, K <  2³¹), and (0 <= P <=100)

For testcase 4-8:    (total lists per day/2 <= X + K <  2³¹), (1 <= N <= 2000), and (0 <= P <=100)

For testcase 9-10:  (0 <= X + K <  2³¹), (1 <= N <= 2000), and (0 <= P <=100)

Output

For each day, first line print “DAY #{X}”for day X, and next line print out sorted list of treated patients (in Panda Hospital) name and age separated by space e.g. “{NAME} {AGE}”, each patient separated by new line, and the end of the list print the income of Panda Hospital at that day with format “INCOME TODAY: {Y}” for Y income. (refers to sample output)

If there is no one to print, you still need to print the day and income

Sample Input  Download

Sample Output  Download

Tags

Discuss