P1937 [USACO10MAR] Barn Allocation G

农夫约翰最近开了一个新的牲口棚。因为其中的一些畜栏风景更好，所以奶牛们向约翰发出了希望分配畜栏的申请。 牲口棚有 $N$ 个畜栏 $(1 \le N \le 100,000)$，方便起见，我们把它们编号为 $1 \sim N$，畜栏 $i$ 能容纳 $C_i$ 头牛 $(1 \le Ci \le 100,000)$。第 $i$ 头牛申请为它分配 $A_i$ 到 $B_i$ 的编号连续的畜栏来让它散步 $(1 \le A_i \le B_i \le N)$。换言之，这头奶牛希望能自由地访问畜栏 $A_i \sim B_i$，而为了满足它的要求，你需要在 $A_i \sim B_i$ 范围内的畜栏中为它预留至少一单位容量。 给出 $M$ 个畜栏分配请求 $(1 \le M \le 100,000)$，回答最多能满足多少头牛的要求而不增加额外的畜栏。

第一行包括两个以空格隔开的正整数：$N,M$。 第二行到第 $N+1$ 行：第 $i+1$ 行每行包括一个整数：$C_i$。 第 $N+2$ 到第 $N+M+1$ 行：第 $i+N+1$ 行每行包括两个整数 $A_i,B_i$。

仅一行：能满足的最大要求数。

考虑以下例子： ```plain 畜栏号: 1 2 3 4 5 +---+---+---+---+---+ 容纳空间: | 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$。 Source: USACO 2010 March Gold Translator: @chrome01, @Hootime