题目描述

Bj0rn 正在准备在《Guitar Hero Live》中打出最高分。他会完美击中所有音符，普通音符每个得 $1$ 分。

游戏中还有一种机制叫 Hero Power，与旧作中的 Star Power 类似。谱面中有若干段星形音符，称为 SP 短语。处于一个 SP 短语的第一个音符和最后一个音符之间时，玩家可以给 SP 表充能。可以从第一个音符的精确时刻开始充能，也可以一直充到最后一个音符的精确时刻；也可以中途暂停。充入的时间可以保存，不必立刻使用，也可以由多个 SP 短语累计获得。

只要 SP 表中有正的时间，玩家就可以在任意时刻激活 SP。激活后，SP 表开始流逝，直到变为 $0$。在激活期间，只要 SP 表仍为正，击中的音符都值 $2$ 分。

边界规则如下：

• 如果在某个音符的精确时刻激活 SP，该音符已经算作 $2$ 分；
• 如果某个音符恰好位于 SP 结束的精确时刻，因为此时 SP 表刚好变为 $0$，该音符只值 $1$ 分。

激活 SP 有一个副作用：如果一次 SP 激活与一个 SP 短语发生重叠，并且在重叠期间 SP 表为正，那么这个 SP 短语会退化成普通音符，不能再用于充能。

特别地，如果某个 SP 短语的第一个音符恰好在 SP 表变为 $0$ 的精确时刻被击中，则该短语不会退化。你也可以在短语中途激活 SP，但之后与激活重叠的部分会使该短语失效，不能再继续从该短语充能。

请帮助 Bj0rn 选择最优策略，求能够得到的最大分数。

输入格式

第一行包含两个整数 $n,p$：

• $1 \le n \le 50000$，表示音符数量；
• $0 \le p \le 100$，表示 SP 短语数量。

第二行包含 $n$ 个严格递增的整数 $t_i$，表示所有音符出现的时间，单位为毫秒，满足：

接下来 $p$ 行，每行包含两个整数 $s_i,e_i$，表示第 $i$ 个 SP 短语的开始和结束时间，满足：

保证每个 SP 短语的开始和结束位置都有音符。SP 短语互不重叠，并按时间升序给出。

输出格式

输出一个整数，表示最大得分。

输入输出样例 #1

输入 #1

3 1
0 10 20
0 10

输出 #1

4

输入输出样例 #2

输入 #2

6 1
0 10 20 26 40 50
0 40

输出 #2

9

输入输出样例 #3

输入 #3

10 2
0 10 20 30 40 50 60 70 80 90
0 40
70 80

输出 #3

14