$\text{Ysgg}$ 有一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，以及 $q$ 个区间。

第 $i$ 个区间由两个整数 $l_i,r_i$ 描述，表示序列中的位置 $l_i,l_i+1,\ldots,r_i$。

在计算这些区间的价值之前，$\text{Ysgg}$ 可以将序列 $a$ 中的元素任意重新排列一次。重新排列后，第 $i$ 个区间的价值定义为

$$\sum_{j=l_i}^{r_i} a_j.$$

$\text{Ysgg}$ 希望所有 $q$ 个区间的价值之和尽可能大。

请你求出这个最大值。

注意，$\text{Ysgg}$ 只能在计算所有区间的价值之前对序列重新排列一次。之后的所有区间均在同一个排列后的序列上计算。

输入

第一行包含两个整数 $n$ 和 $q$（$1 \le n,q \le 2\cdot 10^5$），分别表示序列长度和区间数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 2\cdot 10^5$），表示序列中的元素。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个区间为 $[l_i,r_i]$。

输出

输出一个整数，表示经过最优重新排列后，所有 $q$ 个区间的价值之和的最大值。

注意，答案可能超过 $32$ 位有符号整数能够表示的范围。

样例

Input1

3 3
5 3 2
1 2
2 3
1 3

Output1

25

说明

在样例中，位置 $1,2,3$ 分别被 $2,3,2$ 个区间覆盖。

因此，可以将最大的元素 $5$ 放在位置 $2$。例如，将序列重新排列为

$$[3,5,2].$$

此时三个区间的价值依次为：

• 区间 $[1,2]$ 的价值为 $3+5=8$；
• 区间 $[2,3]$ 的价值为 $5+2=7$；
• 区间 $[1,3]$ 的价值为 $3+5+2=10$。

因此，所有区间的价值之和为

$$8+7+10=25.$$

可以证明不存在更优的重新排列方式，所以答案为 $25$。

数据范围

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

定义以下特殊性质：

• 特殊性质 A：$q=1$；
• 特殊性质 B：对于所有 $1\le i\le q$，均有 $l_i=r_i$；
• 特殊性质 C：$a_1=a_2=\cdots=a_n$；
• 特殊性质 D：所有区间完全相同，即对于所有 $1\le i\le q$，均有 $l_i=l_1$ 且 $r_i=r_1$。

各测试点的数据范围如下：

测试点编号	$n$	$q$	特殊性质
$1$	$\le 5$		无
$2$	$\le 20$
$3\sim 4$	$\le 500$
$5\sim 6$	$\le 2000$
$7$	$\le 2\cdot 10^5$	$1$	A
$8$		$\le 2\cdot 10^5$	B
$9$			C
$10$			D
$11\sim 12$	$\le 5\cdot 10^4$		无
$13\sim 14$	$\le 10^5$
$15\sim 20$	$\le 2\cdot 10^5$