题目描述

John 最近开了一个新的牲口棚，他需要处理一些奶牛重新分配畜栏的申请。

牲口棚有 $N$ 个畜栏，编号为 $1 \dots N$ ，畜栏 $i$ 能容纳 $C_i$ 只牛。第 $i$ 只牛需要 $A_i$ 到 $B_i$ 这一连续段的畜栏，换言之，这只牛需要 $A_i$ 到 $B_i$ 之间的畜栏空出位置来供它散步。

给出 $M$ 个畜栏分配请求，回答最多能满足多少只牛的要求。

输入格式

第 $1$ 行输入两个用空格隔开的整数 $N$ 和 $M$ 。

接下来 $N$ 行，每行输入一个整数 $C_i$ 。

接下来 $M$ 行，每行输入 $2$ 个整数 $A_i$ 和 $B_i$ 。

输出格式

输出一个整数，表示最多能够被满足的要求数。

输入输出样例 #1

输入 #1

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

输出 #1

3

如下图分配，最多可以给1、3、4满足要求。

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

数据范围

对于所有数据，$1 \le n \le 2 \times 10^5$，$1 \le m \le 4 \times 10^5$。