问题 A: 奇怪的宇宙

内存限制:12 MB 时间限制:5.000 S
评测方式:文本比较 命题人:
提交:553 解决:44

题目描述

L.I最近掉进了一个时空漩涡,他发现里面有m个平行宇宙,并且每个平行宇宙中都包含了他自己所在宇宙中的部分宝藏,包含的是他自己宇宙宝藏序号的LR序号中所有的  宝藏。

他自己的宇宙有n个宝藏,宝藏有它本身的价值,宝藏标号从1-n

他想带走m个宇宙中每个宇宙中价值最大的一些宝藏,请你计算L.I最后带走的宝藏价值总和。 

(请注意本题空间限制为10m)

输入

第一行两个数字nmn个宝藏,和m个宇宙。(1<=n , m <= 5e5)

第二行n个数字(1 <= ai < 1e9),第i个数字代表第i个宝藏的价值,它的序号为i

接下来m行每行两个数字,代表每个宇宙包含L.I宇宙第L个到第R个宝藏。(1 <= L,R <= n , 注意第一个数字不一定小于等于第二个数字)

输出

最后的价值之和。

样例输入 复制

8 4
1 1 8 9 7 8 8 9
1 5
4 8
5 7
1 8

样例输出 复制

61

提示

第一个宇宙选择了第四个价值为9的宝藏。
第二个宇宙选择了第四个和第八个价值为9的宝藏。
第三个宇宙选择第六个和第七个价值为8的宝藏。
第四个宇宙选择了第四个和第八个价值为9的宝藏。
所以宝藏价值是9+9*2+8*2+9*2 = 61

来源/分类