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 {

    private static int N, M;
    private static int[] A, B, C;

    private static void read() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[N];
        B = new int[M];
        C = new int[M];
        for (int i = 0; i < N; i += 1) {
            A[i] = Integer.parseInt(sc.next());
        }
        for (int i = 0; i < M; i += 1) {
            B[i] = Integer.parseInt(sc.next());
            C[i] = Integer.parseInt(sc.next());
        }
    }

    public static void main(String[] args) {
        read();

        List<List<Integer>> XY = new ArrayList<>();
        for (int Ai : A) {
            List<Integer> list = new LinkedList<>();
            list.add(1); list.add(Ai);
            XY.add(list);
        }
        for (int i = 0; i < M; i += 1) {
            List<Integer> list = new LinkedList<>();
            list.add(B[i]); list.add(C[i]);
            XY.add(list);
        }

        Collections.sort(XY, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                Integer Y1 = o1.get(1);
                Integer Y2 = o2.get(1);
                return Y2.compareTo(Y1);
            }
        });

        long max = 0;
        int remaining = N;
        boolean getReturn = false;
        for (List<Integer> xy : XY) {
            int x = xy.get(0);
            int y = xy.get(1);
            for (int i = 0; i < x; i += 1) {
                max += y;
                remaining -= 1;
                if (remaining == 0) {
                    getReturn = true;
                    break;
                }
            }

            if (getReturn) {
                break;
            }
        }

        System.out.println(max);
    }
}
