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 ≤ l_i ≤ r_i ≤ 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.

Input

The first line contains two space-separated integers n (1 ≤ n ≤ 2⋅10^5) and q (1 ≤ q ≤ 2⋅10^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 ≤ a_i ≤ 2⋅10^5) — the array elements.

Each of the following q lines contains two space-separated integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the i-th query.

Output

In a single line print, a single integer — the maximum sum of query replies after the array elements are reordered.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3 3
5 3 2
1 2
2 3
1 3


Output

25


Input

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


Output

33
import java.util.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {

    void randomShuffle(long[] arr) {
        Random rnd = new Random();
        for (int i = arr.length - 1; i >= 0; i--) {
            int pos = rnd.nextInt(i + 1);
            long temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
        }
    }
    
    public void solve() throws Exception {
        int n = sc.nextInt(), q = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        long[] balance = new long[n];
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
            balance[l]++;
            if (r + 1 < n) {
                balance[r + 1]--;
            }
        }
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                balance[i] += balance[i - 1];
            }
        }
        randomShuffle(a);
        randomShuffle(balance);
        Arrays.sort(a);
        Arrays.sort(balance);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += a[i] * balance[i];
        }
        out.println(ans);
    }
    
    static Throwable uncaught;
    
    BufferedReader in;
    FastScanner sc;
    PrintWriter out;
    
    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            sc = new FastScanner(in);
            solve();
        } catch (Throwable uncaught) {
            Solution.uncaught = uncaught;
        } finally {
            out.close();
        }
    }
    
    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread (null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        if (Solution.uncaught != null) {
            throw Solution.uncaught;
        }
    }

}

class FastScanner {
    
    BufferedReader in;
    StringTokenizer st;
    
    public FastScanner(BufferedReader in) {
        this.in = in;
    }
    
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
    
    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
    
}