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

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