High School Programming League Problems Archive

Thanks to Marcin ISO has a very good plan for locating its bases. Now a new optimization problem has appeared. There are two types of units in each base: Green Rangers and Red Dragons. Utilization of these units depends on the mission type. In the case of a green alarm (G), Rangers are sent out, and in the case of a red alarm (R), Dragons are sent out; finally, in the case of a yellow alarm (Y), it is necessary to send out both types of units.

When the alarms are reported to ISO officers, they are able to determine the time needed to complete particular missions, but they have a problem with determining the optimal intervention schedule. Suppose, that there is only one Rangers unit and one Dragons unit in the base, and the times needed to complete all missions are exactly known. How should the mission schedule be arranged so as to minimize the sum of the completion times of all missions?

Input

You are given m < 1000 - the number of missions to complete. In the next m lines, for each mission there is given the mission type (one of the letters: {R, G, Y}) and a natural number not larger then 100 - the time needed to complete the mission.

Output

Print m+1 numbers. The first m describe the start times of the following missions, and the last number is the sum of completion times of all missions.

Example 1

Input:
3
R 3
G 3
Y 1

Output:
0
0
3
10

Example 2

Input:
3
R 3
G 3
Y 0

Output:
0
0
3
9

Example 3

Input:
3
R 1
G 2
Y 3

Output:
0
0
2
8

Comment

In example 3, at time moment 1 Rangers are waiting for Dragons, who are going to complete their mission at moment 2. Sending the unit to two different missions at the same time and sending only one unit to complete mission Y is prohibited.

Scoring

The score awarded to your program for a given test is computed as C/C_p, where C_p is the sum of completion times obtained by your program, and C is some reference value). The overall score of the program is the sum of scores obtained for the correctly solved tests.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Input data sizes

Test data sizes are given below.

 t    m     l 
 1    12    2s
 2    45    2s
 3    125   2s
 4    175   2s
 5    217   2s
 t - test number
 m - number of missions
 l - time limit

Please note

• Before the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
• For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full set of test cases. (All earlier solutions will be rejudged).