문제
1 × L 격자의 각 칸에 과자가 몇 개 담겨져 있다.
N명의 학생들은 각자 P번째에서부터 K번째 칸까지 위치한 과자를 칸마다 하나씩 가져간다. 그러면 각 학생이 가져갈 과자의 수는 정확히 K-P+1개라고 예상할 수 있다. 하지만 과자의 수가 유한하기 때문에 정확히 K-P+1개의 과자를 가져갈 수 없는 학생도 있을 수 있다.
각 학생은 자신이 가져갈 수 있는 과자를 모두 가져갈 수 있을 때만 행복을 느낀다. 각 칸에 있는 과자의 수와 각 학생의 P와 K가 주어질 때, 행복한 학생을 최대한 많게 하여라.
입력
첫 번째 줄에 L과 N (1 ≤ L, N ≤ 100,000) 이 주어진다.
두 번째 줄부터 L개의 줄에는 Ci가 주어진다. (1 ≤ Ci ≤ 100,000)
L+2 번째 줄부터 N개의 줄에는 각 학생의 Pi, Ki 값이 주어진다. (1 ≤ Pi ≤ Ki ≤ L)
출력
행복한 학생의 수의 최댓값을 출력한다.
예제1
입력
54
1
3
2
1
3
13
25
23
45
출력
3
힌트
출처
USACO 2010 March Gold Barn Allocation