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.*;
	
 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
    public static void main(String[] args) {
    	
        Scanner sc = new Scanner(System.in);
        

        int N = sc.nextInt();
        int M = sc.nextInt();
        long[] a = new long[N];
        for(int i=0;i<N;i++) {
            a[i] = sc.nextLong();        	
        }
        Arrays.sort(a);
        long[] b = new long[M];
        long[] c = new long[M];
        for(int i=0;i<M;i++) {
            b[i] = sc.nextLong();         	
            c[i] = sc.nextLong();
        }
        quick_sort(c,b);
        long[] k = new long[3*N];
        int cnt=0;
        int bcnt=0,acnt=0;
        while(cnt<N) {
        	if(M-bcnt-1<0) {
        		bcnt=M-1;
        		c[M-bcnt-1]=0;
        	}
        	if(a[N-acnt-1]<0) {
        		acnt--;
        		a[N-acnt-1]=0;
        	}
        	if(a[N-acnt-1]>c[M-bcnt-1]) {
        		k[cnt]=a[N-acnt-1];
        		cnt++;
        		acnt++;
        	}else {
        		for(int i=0;i<b[M-bcnt-1];i++) {
        			k[cnt]=c[M-bcnt-1];
        			cnt++;
        		}
        		bcnt++;
        	}
        }
        long ans=0;
        for(int i=0;i<N;i++) {
        	ans=ans+k[i];
        }
        System.out.println(ans);
    }
    
  //クイックソート2（配列2つ）
    static void quick_sort(long[] d, long[] d2) {
  	  quick_sort(d,d2, 0, d.length-1);
    }

    // dのleftからrightまでの間のデータ列をクイックソートする
    static void quick_sort(long[] d, long[] d2, int left, int right) {
        if (left>=right) {
            return;
        }
        long p = d[(left+right)/2];
        int l = left, r = right;
        long tmp;
        while(l<=r) {
            while(d[l] < p) { l++; }
            while(d[r] > p) { r--; }
            if (l<=r) {
                tmp = d[l]; d[l] = d[r]; d[r] = tmp;
                tmp = d2[l]; d2[l] = d2[r]; d2[r] = tmp;
                l++; r--;
            }
        }
        quick_sort(d, d2, left, r);  // ピボットより左側をクイックソート
        quick_sort(d, d2, l, right); // ピボットより右側をクイックソート
    }
}