问题描述

JOI 先生在他的家里拥有N棵树。 这些树排成一行，编号从1到N。

这个冬天，JOI 先生决定选择一些树来装饰圣诞灯。每棵树上都被赋予了一个称为“美丽度”的值。将圣诞灯装饰在第i棵树上的美丽度为Ai。

JOI 先生注意到，如果他装饰了相邻的两棵树，光线可能会太亮。 具体来说，对于j = 1, 2, ..., M，已经发现不应该在树Lj，Lj + 1，...，Rj中的两棵或更多的树上放置圣诞灯。

根据这个条件，找到装饰圣诞灯时美丽度的最大总和。

约束条件

• 1 ≤ N ≤ 200000 ($2×10^5$)
• 1 ≤ M ≤ 200000 ($2×10^5$)
• 1 ≤ Ai ≤ 1000000000 ($10^9$) (1 ≤ i ≤ N)
• 1 ≤ Lj ≤ Rj ≤ N (1 ≤ j ≤ M)

输入

输入以以下格式从标准输入中给出。

N M A1 A2 ... AN L1 R1 L2 R2 ... LM RM

输出

在一行中输出圣诞灯的美丽度的最大总和。

子任务

1. ($10$ 分) $N ≤ 16$，$M ≤ 16$
2. ($30$ 分) $N ≤ 300$，$M ≤ 300$
3. ($30$ 分) $N ≤ 4000$，$M ≤ 4000$
4. ($30$ 分) 没有额外限制。

输入示例 1

4 1
1 2 3 8
2 4

输出示例 1

9

在这个示例输入中，如果在树1和树4上装饰圣诞灯，美丽度的总和将达到9，并且是最大的。由于L1 = 2，R1 = 4，因此无法在树2、树3、树4上同时装饰圣诞灯。请注意，不能在树1、树2、树4上装饰圣诞灯。

输入示例 2

5 2
2 3 9 5 6
1 3
2 4

输出示例 2

15

输入示例 3

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

输出示例 3

4912419478