Restaurant Seating Problem

The cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has \( N \) seats in a row, numbered from 1 to \( N \) (where \(1 \le N \le 500\,000\)). Initially, all seats are empty.

Throughout the day, there are \( M \) events (\(1 \le M \le 300\,000\)) that occur sequentially. There are two types of events:

1. Arrival event: A party of size \( p \) (\(1 \le p \le N\)) arrives. Bessie tries to seat the party in a contiguous block of \( p \) empty seats. She always chooses the leftmost available block that is large enough. If no such block exists, the party is turned away.
2. Leaving event: A range \([a, b]\) is given (\(1 \le a \le b \le N\)), and everyone sitting in this range leaves, making these seats available again.

Your task is to determine the total number of parties that are turned away.

Note: When a leaving event occurs, if the newly freed seats are adjacent to other free segments, they merge into a single contiguous block.

inputFormat

The first line contains two integers, \( N \) and \( M \), representing the number of seats and the number of events respectively.

The following \( M \) lines each describe an event. Each event is in one of the two formats:

• A p — a party of size \( p \) arrives.
• L a b — all guests sitting in seats from \( a \) to \( b \) (inclusive) leave.

outputFormat

Output a single integer representing the total number of parties that are turned away.

sample

10 5
A 3
A 4
L 1 3
A 5
A 2

1