题目来源

[USACO10MAR] Barn Allocation G

题目描述

农夫约翰最近开了一个新的牲口棚屋，并且现在接受来自奶牛的分配畜栏请求因为其中的一些畜栏有更好风景。

畜栏包括 $N$ 个畜栏( $1 \le N ≤ 10^5$ )，方便起见，我们把它们编号为 $1 \sim N$，畜栏 $i$ 能容纳 $C_i$ 只牛( $1 \le C_i ≤ 10^5$ )，第 $i$ 只牛需要连续编号畜栏（从 $A_i$ 到 $B_i$ ）来漫步其中，

($1 \le A_i \le B_i \le N$ )，换言之，这只牛想要在编号范围为 $A_i \sim B_i$ 的畜栏漫步（所有它想要畜栏必须实施为它空出位置来供它散步）

给出 $M$ 个畜栏分配请求（ $1 \le M \le 10^5$ ），回答最多能满足多少只牛的要求（不新增加畜栏的前提下）

考虑以下例子：

畜栏号:    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

输入格式

第一行包括两个以空格隔开的正整数：$N$, $M$

第二行到第 $N+1$ 行：第 $i+1$ 行包括一个整数：$C_i$

第 $N+2$ 到第 $N+M+1$ 行：第 $i+N+1$ 包括两个整数 $A_i$、$B_i$

输出格式

仅一行：能满足的最大需要

样例

5 4
1
3
2
1
3
1 3
2 5
2 3
4 5

3