问题 A: 奇怪的宇宙
内存限制：12 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：583
解决：45
题目描述
L.I最近掉进了一个时空漩涡，他发现里面有m个平行宇宙，并且每个平行宇宙中都包含了他自己所在宇宙中的部分宝藏，包含的是他自己宇宙宝藏序号的L到R序号中所有的 宝藏。
他自己的宇宙有n个宝藏，宝藏有它本身的价值，宝藏标号从1-n。
他想带走m个宇宙中每个宇宙中价值最大的一些宝藏，请你计算L.I最后带走的宝藏价值总和。
(请注意本题空间限制为10m)
输入
第一行两个数字n和m，n个宝藏，和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
第二个宇宙选择了第四个和第八个价值为9的宝藏。
第三个宇宙选择第六个和第七个价值为8的宝藏。
第四个宇宙选择了第四个和第八个价值为9的宝藏。
所以宝藏价值是9+9*2+8*2+9*2 = 61