题目描述

牧场主老周新建了一座观景牲口棚。棚里有些位置临窗采光好，奶牛们纷纷递交了「想要散步区域」的申请。

牲口棚里共有 $N$ 个畜栏 $(1 \le N \le 100,000)$，编号 $1 \sim N$，畜栏 $i$ 最多能容纳 $C_i$ 头牛 $(1 \le C_i \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$。

第 $2$ 行到第 $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$。