축사 배정

농부 존(Farmer John)이 새 축사를 열고, 소들에게서 칸 배정 요청을 받고 있습니다. 어떤 칸은 목초지 전망이 더 좋기 때문에 소들이 특정 구간을 원하기 때문입니다.

축사에는 $1$번부터 $N$번까지 번호가 매겨진 칸이 있습니다($1 \le N \le 100000$). $i$번 칸은 동시에 최대 $C_i$마리의 소를 수용할 수 있습니다($1 \le C_i \le 100000$). 각 소는 자유롭게 돌아다닐 연속된 칸 구간 $[A_i, B_i]$를 요청합니다($1 \le A_i \le B_i \le N$). 이 요청을 들어주려면, 그 소가 돌아다니는 동안 구간 $A_i \dots B_i$에 속한 모든 칸에 그 소를 받아들일 여유 용량이 항상 있어야 합니다.

총 $M$개의 요청이 주어집니다($1 \le M \le 100000$). 어떤 요청을 들어주면, 그 소는 자신의 구간에 속한 모든 칸에서 동시에 용량 $1$을 차지합니다. 어떤 칸의 용량도 초과되지 않도록 하면서, 동시에 들어줄 수 있는 요청의 최대 개수를 구하세요.

예를 들어, 칸이 $5$개이고 아래와 같은 용량과 요청을 가진 축사를 생각해 봅시다.

Stall id:    1   2   3   4   5
           +---+---+---+---+---+
Capacity:  | 1 | 3 | 2 | 1 | 3 |
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)

네 요청을 모두 들어줄 수는 없습니다. $3$번과 $4$번 칸의 용량을 넘기기 때문입니다. 하지만 $1$번, $3$번, $4$번 소의 요청은 어떤 칸의 용량도 초과하지 않고 동시에 모두 들어줄 수 있으므로, 이 경우의 최대 개수는 $3$입니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• $2$번째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에는 $i$번 칸의 용량인 정수 $C_i$가 하나 주어집니다.
• $N+2$번째 줄부터 $N+M+1$번째 줄까지: $i+N+1$번째 줄에는 $i$번 소가 요청한 구간을 나타내는 두 정수 $A_i$와 $B_i$가 주어집니다.

• 들어줄 수 있는 요청의 최대 개수를 한 줄에 출력합니다.