Seating

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:

1. 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.
2. 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.

• 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.

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

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.