P1937 [USACO10MAR] Barn Allocation G

题目描述

数轴上有 $N$ 个点，编号为 $1 \dots N$，点 $i$ 能容纳 $C_i$ 条线段覆盖。

有 $M$ 条线段，第 $i$ 条线段覆盖范围为 $[A_i,B_i]$ 。

问数轴上最多能放多少条线段。

输入格式

第一行两个整数 $N,M(1 ≤ N , M ≤ 100,000)$。

下来 $N$ 个整数 $C_i(1 ≤ C_i ≤ 100,000)$。

下来 $M$ 对整数 $A_i、B_i(1 ≤ A_i ≤ B_i ≤ N)$。

输出格式

一行一个整数，即最多能放的线段数目。

输入输出样例 #1

输入 #1

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

输出 #1

3