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{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] A = new int[N];
        int[][] B = new int[2][M];
        long sum = 0;
        Map<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            sum += A[i];
        }
        for(int i = 0; i < M; i++){
            B[0][i] = sc.nextInt();
            B[1][i] = sc.nextInt();
            if(map.containsKey(B[1][i])){
                map.put(B[1][i], map.get(B[1][i])+B[0][i]);
            } else {
                map.put(B[1][i], B[0][i]);
            }
        }
        sc.close();

        Arrays.sort(A);
        int[][] C = new int[2][map.size()];
        int i = 0;
        for(Integer key: map.keySet()){
            C[0][i] = key;
            C[1][i] = map.get(key);
            i++;
        }

        int i_A = 0;
        int i_C = map.size()-1;
        while(i_A < N && i_C >= 0){
            if(A[i_A] < C[0][i_C] && C[1][i_C] > 0){
                sum += C[0][i_C] - A[i_A];
                C[1][i_C]--;
                if(C[1][i_C] == 0)
                    i_C--;
            }
            i_A++;
        }

        System.out.println(sum);
    }
}