The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of $n$ elements (the elements of the array are indexed starting from 1); also, there are $q$ queries, each one is defined by a pair of integers $l_i$, $r_i$ $(1 \le l_i \le r_i \le n)$. You need to find for each query the sum of elements of the array with indexes from $l_i$ to $r_i$, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.
The first line contains two space-separated integers $n$ ($1 \le n \le 2\cdot10^5$) and $q$ ($1 \le q \le 2\cdot10^5$) — the number of elements in the array and the number of queries, correspondingly.

The next line contains $n$ space-separated integers $a_i$ ($1 \le a_i \le 2\cdot10^5$) — the array elements.

Each of the following $q$ lines contains two space-separated integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the $i$-th query.
/**
████████▄     ▄████████ ████████▄     ▄████████    ▄████████  ▄████████
███   ▀███   ███    ███ ███   ▀███   ███    ███   ███    ███ ███    ███
███    ███   ███    █▀  ███    ███   ███    █▀    ███    █▀  ███    █▀
███    ███  ▄███▄▄▄     ███    ███   ███         ▄███▄▄▄     ███
███    ███ ▀▀███▀▀▀     ███    ███ ▀███████████ ▀▀███▀▀▀     ███
███    ███   ███    █▄  ███    ███          ███   ███    █▄  ███    █▄
███   ▄███   ███    ███ ███   ▄███    ▄█    ███   ███    ███ ███    ███
████████▀    ██████████ ████████▀   ▄████████▀    ██████████ ████████▀

 */
#include <bits/stdc++.h>
using namespace std;
#define DedSec ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define MOD 998244353
#define all(x) (x).begin(), (x).end()

int dr[] ={-1,1,0,0};
int dc[] = {0,0,1,-1};

ll BinomialCoefficient(const int n, const int k) {
    vector<ll> aSolutions(k);
    aSolutions[0] = n - k + 1;

    for (int i = 1; i < k; ++i) {
        aSolutions[i] = aSolutions[i - 1] * (n - k + 1 + i) / (i + 1);
    }

    return aSolutions[k - 1];
}

void solve() {
    int n,q;
    cin>>n>>q;
    vector<ll>nums(n);
    for(int i=0;i<n;i++) cin>>nums[i];
    sort(all(nums),greater<>());
    vector<pair<ll,ll>>queries{};
    ll start=LLONG_MIN,end=LLONG_MAX;
    for(int i=0;i<q;i++){
        pair<ll,ll>mp;
        cin>>mp.first>>mp.second;
        ll ts = start;
        ll te = end;
        start = max(start,mp.first);
        end = min(end,mp.second);
        if(end<start){
            start = ts;
            end = te;
        }
        queries.push_back(mp);
    }
    vector<ll>result(n,-1);
    for(ll i=start-1;i<end;i++){
        result[i] = nums[i-start+1];
        nums[i-start+1] = -1;
    }
    int p = 0;
    for(int i=0;i<n;i++){
        if(result[i]!=-1) continue;
        while(nums[p]==-1) p++;
        result[i] = nums[p];
        p++;
    }
    vector<ll>prefix(n+1,0);
    for(int i=1;i<=n;i++) prefix[i] = result[i-1]+prefix[i-1];
    ll sum = 0;
    for(auto& pr : queries){
        sum+= prefix[pr.second]-prefix[pr.first-1];
    }
    cout<<sum<<endl;
}

int main() {
    DedSec
//    ll t;cin>>t;
//    while (t--)
        solve();

    return 0;
}