2749 : 과자 가져가기 2
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 8 회
- 시도횟수
- 30 회
문제
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)
출력형식
행복한 학생의 수의 최댓값을 출력한다.
입력 예5 4 1 3 2 1 3 1 3 2 5 2 3 4 5 |
출력 예3 |
Hint!
