题目描述

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered 1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow i may request a contiguous interval of stalls (A_i, B_i) in which to roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to wander among all the stalls in the range A_i..B_i (and the stalls must always have the capacity for her to wander).

Given M (1 <= M <= 100,000) stall requests, determine the maximum number of them that can be satisfied without exceeding stall

capacities.

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

畜栏包括N个畜栏(1 ≤ N ≤ 100,000)，方便起见，我们把它们编号为1..N，畜栏i能容纳Ci只牛(1 ≤ Ci ≤ 100,000)，第i只牛需要连续编号畜栏（从Ai到Bi）来漫步其中，

(1 ≤ Ai ≤ N; Ai ≤ Bi ≤ N)，换言之，这只牛想要在编号范围为Ai..Bi的畜栏漫步（所有它想要畜栏必须实施为它空出位置来供它散步）

给出M个畜栏分配请求（1 ≤ M ≤ 100,000），回答最多能满足多少只牛的要求（不增加另外畜栏）

考虑以下例子：

畜栏号:    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行包括一个整数：Ci

第N+2到第N+M+1行：第i+N+1 包括两个整数Ai、Bi

输出格式

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

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

3

提示

Source: USACO 2010 March Gold

Translator: @chrome01