URI Online Judge | 1246

Parking Lot

Maratona de Programação da SBC Brasil

Timelimit: 1

A parking lot uses a terrain where vehicles have to be stored in a single line, one behind the other. The tariff is a fixed value of R$ 10.00 per vehicle parked charged on entry, regardless of its size and time of permanence. As parking is very crowded, Not all vehicles entering the parking can get a place to park.

When a vehicle arrives at the parking, the attendant first determines if there is vacancy for that vehicle. For this, he roams the parking lot, from beginning to end, looking for a space that is vacant and has length greater than or equal to the length of the vehicle. To save your time and energy, the attendant chooses the first space it finds appropriate, ie, the space closest to the beginning.

Once found the vacancy for the vehicle, the attendant back to the entrance of the parking lot, take the car and park at the beginning of the space found. If the attendant does not find adequate space, the vehicle does not enter the parking and the tariff is not charged. After parked, the vehicle is not moved until the time it leaves the parking area.

The owner of the parking lot is concerned with whether the attendants are properly charged the tariff of vehicles parked and asked you to write a program that, given the list of arrivals and departures of vehicles in the parking lot, determines the total expected billing.


The input consists of several test cases. The first line of a test case contains two integers C (1 ≤ C ≤ 1000) and N (1 ≤ N ≤ 10000) that respectively indicating the length in meters of the parking lot and the total number of events (arrivals and departures of vehicles). Each of the next N lines describes an arrival or departure. For a vehicle arrived, the line contains the letter 'C', followed by two integers P (1000 ≤ P ≤ 9999) and Q (1 ≤ Q ≤ 1000), all separated by a blank space. P indicates the vehicle plate and Q their length. For a vehicle departure, the row contains the letter 'S' followed by an integer P, separated by a blank space, where P indicates the vehicle plate. Actions are given in chronological order, ie, in the order they happen.

At the beginning of each test case in the parking lot is empty. In the input file, a vehicle leaves the parking lot only if is actually parked, and the plate of a vehicle that reaches the parking lot is never equal to the plate of a vehicle already parked.


For each test case your program should print a line containing an integer representing the billing of the parking lot in reais.

Sample Input Sample Output

10 7
C 1234 5
C 1111 4
C 2222 4
C 4321 3
S 1111
C 2002 6
C 4321 3
30 10
C 1000 10
C 1001 10
C 1002 10
S 1000
S 1002
C 1003 20
S 1001
C 1004 20
S 1004
C 1005 30
20 10
C 1234 20
C 5678 1
S 1234
C 1234 20
C 5678 1
S 1234
C 5678 1
C 1234 20
C 5555 1
S 5678