题目描述

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

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

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

输入格式

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

第 $2$ 行到 $N+1$ 行：第 $i+1$ 行一个整数 $C_i$。

第 $N+2$ 到 $N+M+1$ 行： 第 $i+N+1$ 行 $2$ 个整数 $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)

数据规模与约定

$1\le N,M\le 10^5$，对 $\forall i \in [1,n]$ 都有 $1\le C_i \le 10^5$，$1\le A_i\le B_i\le N$。