Seating

Time limit1sMemory limit128 MB

Summary

Track seats in a row under arrivals needing the lowest block of p empty seats and range departures; count the parties turned away.

Level: Medium7 of 10
Topics: Segment tree, Binary search, Array, Greedy
Solved: No attempts yet

Problem

To earn some extra money, the cows have opened a milkshake restaurant in their barn. The restaurant has $N$ seats in a single row ( $1 \le N \le 500000$ ), and every seat is empty at the start of the day.

Over the course of the day, $M$ events happen in sequence ( $1 \le M \le 300000$ ). Each event is one of two kinds:

A party of size $p$ arrives ( $1 \le p \le N$ ). Bessie wants to seat the whole party in a block of $p$ consecutive empty seats. If this is possible, she seats them at the lowest-numbered position where they fit. If it is impossible, the party is turned away.
A range $[a, b]$ is given ( $1 \le a \le b \le N$ ), and everybody sitting in that range of seats leaves (those seats all become empty).

Count the total number of parties that are turned away during the day.

Input

Line 1: Two space-separated integers $N$ and $M$ .
Next $M$ lines: Each line describes one event. A line A p means a party of size $p$ arrives; a line L a b means every customer in the seat range $[a, b]$ leaves.

Output

Line 1: The number of parties that are turned away.

Notes

Here is a walkthrough of the first example. There are 10 seats and 4 events. First, a party of 6 arrives and takes seats 1–6. Then everybody in seats 2–4 leaves. Next, a party of 5 arrives, but no block of 5 consecutive empty seats exists, so it is turned away. Finally, a party of 2 arrives and takes the empty seats 2–3. Only the third party is turned away.

Examples3

Example 1
Input
```
10 4
A 6
L 2 4
A 5
A 2
```
Expected output
```
1
```
Example 2
Input
```
10 3
A 3
A 3
A 4
```
Expected output
```
0
```
Example 3
Input
```
5 2
A 3
A 3
```
Expected output
```
1
```