Seating [Travis Hance, 2012]

To earn some extra money, the cows have opened a restaurant in their barn
specializing in milkshakes.  The restaurant has N seats (1 <= N <= 500,000)
in a row. Initially, they are all empty. 

Throughout the day, there are M different events that happen in sequence at
the restaurant (1 <= M <= 300,000).  The two types of events that can
happen are:

1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party
in a contiguous block of p empty seats. If this is possible, she does so in
the lowest position possible in the list of seats.  If it is impossible,
the party is turned away.

2. A range [a,b] is given (1 <= a <= b <= N), and everybody in that range of
seats leaves.

Please help Bessie count the total number of parties that are turned away
over the course of the day.

PROBLEM NAME: seating

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M.

* Lines 2..M+1: Each line describes a single event.  It is either a
        line of the form "A p" (meaning a party of size p arrives) or
        "L a b" (meaning that all cows in the range [a, b] leave).

SAMPLE INPUT (file seating.in):

10 4
A 6
L 2 4
A 5
A 2

INPUT DETAILS:

There are 10 seats, and 4 events.  First, a party of 6 cows arrives.  Then
all cows in seats 2..4 depart.  Next, a party of 5 arrives, followed by a
party of 2.

OUTPUT FORMAT:

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

SAMPLE OUTPUT (file seating.out):

1

OUTPUT DETAILS:

Party #3 is turned away.  All other parties are seated.