Parking Lot

Interview

Time limit2sMemory limit512 MB

Summary

Simulate a single-line parking lot where each arriving vehicle takes the first free gap from the entrance that fits, and total the fees for vehicles that park.

Level: Medium6 of 10
Topics: Simulation, Implementation, Array, Intervals
Solved: No attempts yet

Problem

A parking lot uses a strip of land where vehicles have to be kept in a single line, one behind another. The fee is fixed at 10 reais per parked vehicle and is charged at the entrance, regardless of the size of the vehicle and how long it stays. The lot is very busy, so not every vehicle that arrives gets a place to park.

When a vehicle arrives, the attendant first decides whether there is room for that vehicle. He walks the lot on foot, from the entrance to the far end, looking for a space that is free and whose length is greater than or equal to the length of the vehicle. To save time and effort, the attendant picks the first suitable space he finds, that is, the space closest to the entrance.

Once the space is found, the attendant walks back to the entrance, takes the vehicle and parks it at the beginning of that space. If the attendant finds no suitable space, the vehicle does not enter the lot and no fee is charged. After it is parked, a vehicle is not moved until the moment it leaves the lot.

The owner of the lot wants to know whether the attendants have charged the parked vehicles correctly. Given the list of arrivals and departures, write a program that determines the expected total revenue.

Input

The input holds several test cases. The first line of a test case contains two integers $C$ and $N$ ( $1 \le C \le 1000$ , $1 \le N \le 10000$ ). $C$ is the length of the parking lot in metres and $N$ is the total number of events, counting arrivals and departures. Each of the next $N$ lines describes one arrival or one departure.

A line for an arrival contains the letter C followed by two integers $P$ and $Q$ ( $1000 \le P \le 9999$ , $1 \le Q \le 1000$ ), separated by single blanks. $P$ is the licence plate of the vehicle and $Q$ is its length. A line for a departure contains the letter S followed by one integer $P$ , separated by a single blank, where $P$ is the licence plate of the vehicle. The events are given in chronological order.

At the start of each test case the lot is empty. A vehicle leaves the lot only if it is really parked, and the plate of an arriving vehicle is never equal to the plate of a vehicle already parked. The input ends at end of file.

Output

For each test case print one line holding an integer, the revenue of the parking lot in reais.

Examples5

Example 1

Input

Expected output

30
50
40

Example 2
Input
```
1 1
C 1000 1
```
Expected output
```
10
```
Example 3
Input
```
1 3
C 1000 2
C 1000 1000
C 9999 7
```
Expected output
```
0
```

Example 4

Input

Expected output

Example 5

Input

Expected output