Barn Stall Allocation

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures. The barn comprises \(N\) stalls conveniently numbered \(1 \ldots N\); stall \(i\) has capacity \(C_i\) cows. Each cow request is given as a contiguous interval \((A_i, B_i)\) meaning the cow wants to roam through all stalls in the range \(A_i \ldots B_i\). Selecting a request uses one unit of capacity from every stall in the interval, and the total usage at each stall cannot exceed its capacity.

Formally, you are given an integer \(N\) (where \(1 \le N \le 10^5\)) and an array \(C = [C_1, C_2, \dots, C_N]\) with \(1 \le C_i \le 10^5\). Then, you are given an integer \(M\) (where \(1 \le M \le 10^5\)) and \(M\) requests. The \(i\)th request is described by two integers \(A_i\) and \(B_i\) satisfying \(1 \le A_i \le B_i \le N\). Choosing a request subtracts \(1\) from each \(C_j\) for every \(j\) in the interval \([A_i, B_i]\). Your task is to determine the maximum number of requests that can be satisfied without any stall exceeding its capacity.

Example:

Stall:      1   2   3   4   5
Capacity:   1   3   2   1   3
Cow 1 (1,3): XXXXXXXXXXX
Cow 2 (2,5):     XXXXXXXXXXXXXXX
Cow 3 (2,3):     XXXXXXX
Cow 4 (4,5):             XXXXXXX

</p>

In this case, by satisfying requests from Cow 1, Cow 3 and Cow 4, Farmer John can meet 3 requests in total whereas satisfying all would exceed the capacities at some stalls.

inputFormat

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

The second line contains \(N\) integers \(C_1, C_2, \dots, C_N\) representing the capacities of the stalls.

Then \(M\) lines follow. Each of these lines contains two integers \(A_i\) and \(B_i\), representing a request for the contiguous interval of stalls from \(A_i\) to \(B_i\).

\(1 \le N, M \le 10^5\), \(1 \le C_i \le 10^5\), and \(1 \le A_i \le B_i \le N\).

outputFormat

Output a single integer representing the maximum number of stall requests that can be satisfied without exceeding the capacity of any stall.

sample

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

3

</p>