题目描述

已知长度n的整数序列。有q个询问，查询A[l]..A[r]之和，并统计所有询问的总和。

现在请你来重新排列序列中的数字，使得这个总和最大。

输入格式

第一行，正整数n,q. (1<=n, q<=2*10$^5$)

第二行，n个正整数(值不超过2*10$^5$ )，表示这个整数序列。

接下来 q 行，每行两个整数 l,r (1<=l<=r<=n)，表示 q 个询问。

输出格式

一个整数，表示答案。

样例

输入#1

3 3
5 3 2
1 2
2 3
1 3

输出#1

25

输入#2

5 3
5 2 4 1 3
1 5
2 3
2 3

输出#2

33

数据范围与提示

样例1： 将序列5,3,2调整为3,5,2

样例2： 将序列5,2,4,1,3调整为3,4,5,1,2