Description

Farmer John has recently opened a new barn and is now accepting stall-allocation requests from cows, since some stalls have better views.

The barn contains $N$ stalls ($1 \le N \le 100{,}000$), labeled $1$ to $N$ for convenience. Stall $i$ can hold $C_i$ cows ($1 \le C_i \le 100{,}000$). The $i$-th cow wants to stroll in a contiguous range of stalls from $A_i$ to $B_i$ ($1 \le A_i \le B_i \le N$). In other words, this cow wants access to every stall in the interval $[A_i, B_i]$, and to satisfy this request you must reserve one unit of capacity in every stall of that interval for this cow.

Given $M$ stall-allocation requests ($1 \le M \le 100{,}000$), determine the maximum number of cows whose requests can be satisfied (without building additional stalls).

Input Format

• The first line contains two space-separated integers: $N, M$.
• Lines $2$ to $N+1$: line $i+1$ contains a single integer $C_i$.
• Lines $N+2$ to $N+M+1$: line $i+N+1$ contains two integers $A_i, B_i$.

Output Format

Output a single line with the maximum number of requests that can be satisfied.

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

3

Hint

Consider the following example:

畜栏号:      1   2   3   4   5
           +---+---+---+---+---+
容纳空间:   | 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)

John clearly cannot satisfy all requests, since stalls $3$ and $4$ are over-requested.

After testing, we find that we can satisfy cows $1, 3, 4$, so the answer for this testdata is $3$.

Source: USACO 2010 March Gold

Translator: @chrome01

Translated by ChatGPT 5