You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

畜栏包括 $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$ 的畜栏漫步（所有它想要畜栏必须实施为它空出位置来供它散步）。

给出 $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$。

输出格式

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

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

3

提示

考虑以下例子：

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