Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS08ISO3 - Intergalactic Security Organization III

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/Cp, where Cp 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).

Added by:kuszi
Date:2009-04-14
Time limit:0.400s-0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CLOJURE NODEJS OBJC PERL6 SQLITE VB.NET
Resource:High School Programming League 2008/09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.