You have N cards. On the i-th card, an integer A_i is written.

For each j = 1, 2, ..., M in this order, you will perform the following operation once:

Operation: Choose at most B_j cards (possibly zero). Replace the integer written on each chosen card with C_j.

Find the maximum possible sum of the integers written on the N cards after the M operations.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq A_i, C_i \leq 10^9
* 1 \leq B_i \leq N

Input

Input is given from Standard Input in the following format:


N M
A_1 A_2 ... A_N
B_1 C_1
B_2 C_2
\vdots
B_M C_M


Output

Print the maximum possible sum of the integers written on the N cards after the M operations.

Examples

Input

3 2
5 1 4
2 3
1 5


Output

14


Input

10 3
1 8 5 7 100 4 52 33 13 5
3 10
4 30
1 4


Output

338


Input

3 2
100 100 100
3 99
3 99


Output

300


Input

11 3
1 1 1 1 1 1 1 1 1 1 1
3 1000000000
4 1000000000
3 1000000000


Output

10000000001
import java.util.*;

public class Main {
    static long mod = 1000000007;

    static class Hand {
        int b, c;
        public Hand(int b, int c) {
            this.b = b;
            this.c = c;
        }
        public String toString() {
            return String.format("(%d, %d)", b, c);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer[] lis = new Integer[n];
        Hand[] hands = new Hand[m];

        for (int i = 0; i < n; ++i) {
            lis[i] = sc.nextInt();
        }
        for (int i = 0; i < m; ++i) {
            int b = sc.nextInt();
            int c = sc.nextInt();
            hands[i] = new Hand(b, c);
        }

        Arrays.sort(lis, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        Arrays.sort(hands, new Comparator<Hand>() {
            public int compare(Hand a, Hand b) {
                return b.c - a.c;
            }
        });

        long sum = 0;
        int i = 0;
        int j = 0;
        while (i < n) {
            if (j < m) {
                if (lis[i] >= hands[j].c) {
//                    System.out.println(String.format("add: lis[%d], %d => %d", i, lis[i], sum + lis[i]));
                    sum += lis[i++];
                } else {
                    for (int k = 0; k < hands[j].b && i < n; ++k) {
                        if (lis[i] >= hands[j].c) {
                            break;
                        }

                        sum += hands[j].c;
                        i += 1;
                    }
                    j++;
//                     long x = Math.min(n - i, hands[j].b);
// //                    System.out.println(String.format("add: lis[%d]: %d, hand[%d]:%s => %d", i, lis[i], j, hands[j].toString(), sum + hands[j].c * x));
//                     sum += hands[j].c * x;
//                     i += x;
//                     j++;
                }
            } else {
//                System.out.println(String.format("add: lis[%d], %d => %d", i, lis[i], sum + lis[i]));
                sum += lis[i++];
            }
        }
        System.out.println(sum);
    }
}
