USACO 2010 March Gold Barn Allocation- 과자 가져가기 2 > 문제은행 : 정보올림피아드&알고리즘




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!

위 그림은 예제의 상태를 나타내는 그림이다. 학생 2가 2, 5번째 칸에 있는 과자를 가져가고 학생 1, 학생 3, 학생 4가 자신이 가져갈 수 있는 과자를 모두 가져간다면 행복한 학생은 3명이 되어 최대이다. 모든 학생을 전부 행복하게 하기에는 3번째 칸과 4번째 칸의 과자의 수가 부족하기 때문에 불가능하다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP