Barn Allocation

Farmer John has opened a new barn and is accepting stall-allocation requests from his cows, since some stalls have a nicer view of the pastures.

The barn has $N$ stalls numbered $1$ through $N$ ($1 \le N \le 100000$); stall $i$ can hold at most $C_i$ cows at the same time ($1 \le C_i \le 100000$). Each cow requests a contiguous interval of stalls $[A_i, B_i]$ ($1 \le A_i \le B_i \le N$) in which to roam. To grant such a request, every stall in the range $A_i \dots B_i$ must have spare capacity for that cow the whole time she wanders.

You are given $M$ requests ($1 \le M \le 100000$). Granting a request makes the cow occupy one unit of capacity in every stall of her interval simultaneously. Determine the maximum number of requests that can be granted at once so that no stall's capacity is ever exceeded.

For example, consider a barn with $5$ stalls whose capacities and requests are shown below:

Stall id:    1   2   3   4   5
           +---+---+---+---+---+
Capacity:  | 1 | 3 | 2 | 1 | 3 |
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)

All four requests cannot be granted together, because stalls $3$ and $4$ would exceed their capacity. However, cows $1$, $3$, and $4$ can all be granted at the same time without exceeding any capacity, so the maximum here is $3$.

• Line 1: two space-separated integers $N$ and $M$.
• Lines $2$ to $N+1$: line $i+1$ contains one integer $C_i$, the capacity of stall $i$.
• Lines $N+2$ to $N+M+1$: line $i+N+1$ contains two integers $A_i$ and $B_i$, the interval requested by cow $i$.

• A single line containing the maximum number of requests that can be granted.