该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

排列查询

有 \(n\) 个数, \(a_{1}, a_{2}, \ldots, a_{n}\) 。有 \(q\) 次询问，第 \(i\) 次询问为两个正整数 \(l_{i}, r_{i}, (1 \leq l_{i} \leq r_{i} \leq n)\) ，查询下标在区间 \(\left[l_{i}, r_{i}\right]\) 内的数的和。

这个问题太简单了。现在倒过来，已知所有的查询，你可以将 \(n\) 个数任意排列，使得所有查询结果的和最大。求最大的查询结果的和。

输入格式

第一行有两个数 \(n(1 \leq n \leq 2 \cdot 10^{5})\) 和 \(q(1 \leq q \leq 2 \cdot 10^{5})\) ，分别表示数的个数和查询的个数。

第二行为 \(n\) 个数，表示 \(a_{1}, a_{2}, \ldots, a_{n}\) 。

接下来 \(q\) 行，每行为 \(l_{i}\) 和 \(r_{i} (1 \leq l_{i} \leq r_{i} \leq n)\) 。

输出格式

输出最大的查询结果的和。

样例1

输入

3 3
5 3 2
1 2
2 3
1 3
    

输出

25
    

样例2

输入

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

输出

33
    

样例