---

我们来计算初始数组中每个单元格被多少个查询覆盖。可以证明，我们应该将较大的数组元素与较大的覆盖次数对应起来。更正式地说：假设 $b$ 是一个数组，其第 $i$ 个单元格中写的是覆盖第 $i$ 个单元格的查询次数。假设 $a$ 是初始数组。我们对这两个数组进行排序。可以证明，在这种情况下，答案可以通过以下公式计算：

$$\sum_{i=1}^{n} a_i \cdot b_i$$

我们来证明这个结论。考虑某两个下标 $i < j$，以及它们对应的元素 $a[i], a[j]$、$b[i], b[j]$（假设 $a[i] \le a[j]$，$b[i] \le b[j]$）。这些元素对答案的贡献是 $a[i] \cdot b[i] + a[j] \cdot b[j]$。如果我们交换 $a[i]$ 和 $a[j]$，那么这些元素对答案的贡献变为 $a[i] \cdot b[j] + a[j] \cdot b[i]$。我们来看以下差值：

$$a[i] \cdot b[j] + a[j] \cdot b[i] - a[i] \cdot b[i] - a[j] \cdot b[j] = b[j] \cdot (a[i] - a[j]) + b[i] \cdot (a[j] - a[i]) = (b[j] - b[i]) \cdot (a[i] - a[j]) \le 0 $$

因此，交换两个元素会导致总结果不增。这意味着我们的排列是最优的。

现在我们需要足够快地计算出数组 $b$。

为此，可以使用不同的支持区间修改的数据结构（线段树、笛卡尔树等）。但还有一种更简单的方法。

我们创建一个数组 $d$。当有一个查询 $l_i, r_i$ 时，我们将 $d[l_i]$ 增加 $1$，并将 $d[r_i + 1]$ 减少 $1$。通过这种巧妙的方式，我们将区间 $[l_i, r_i]$ 内的所有元素都增加了 $1$。处理完所有查询后，我们需要遍历数组 $d$ 的每个元素。在这个遍历过程中，我们可以轻松计算出数组 $b$ 的所有元素。

现在我们已经准备好得到最终答案。作者解法的时间复杂度为 $O(N \log N + Q)$。

---

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <memory.h>
#include <ctime>
 
using namespace std;
 
#define ABS(a) ((a>0)?a:-(a))
#define MIN(a,b) ((a<b)?(a):(b))
#define MAX(a,b) ((a<b)?(b):(a))
#define FOR(i,a,n) for (int i=(a);i<(n);++i)
#define FI(i,n) for (int i=0; i<(n); ++i)
#define pnt pair <int, int>
#define mp make_pair
#define PI 3.14159265358979
#define MEMS(a,b) memset(a,b,sizeof(a))
#define LL long long
#define U unsigned
 
int a[200100];
int val[200100];
int b[200100];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    FOR(i,0,n)
        scanf("%d",&a[i]);
    sort(a,a+n);
    FOR(i,0,q)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        l--;
        r--;
        val[l]++;
        if (r<n-1)
            val[r+1]--;
    }
    int v=0;
    FOR(i,0,n)
    {
        v+=val[i];
        b[i]=v;
    }
    sort(b,b+n);
    LL res=0;
    FOR(i,0,n)
        res+=(b[i]*1ll*a[i]);
    cout<<res<<endl;
    return 0;
}