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.AbstractMap;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

     static Scanner scanner;

     public static void main(String[] args) {
         scanner = new Scanner(System.in);

         int N=gi();
         int M=gi();
         long[] a=new long[N];
         Pair<Long, Long>[] ps=new Pair[M];

         for(int i=0; i<N;i++) {
        	 a[i]=gl();
         }

         for(int i=0; i<M;i++) {
        	 long b=gl();
        	 long c=gl();
        	 Pair<Long,Long> p=new Pair<Long,Long>(c,b);
        	 ps[i]=p;
         }

         Arrays.parallelSort(a);
         Arrays.parallelSort(ps, Collections.reverseOrder());

         int ind=0;
         long max=0;
         for(int i=0; i<M;i++) {
        	 Pair<Long,Long> p=ps[i];
        	 long b=p.getValue();
    		 long c=p.getKey();
        	 for(int j=0; j<b;j++) {
        		 if(ind>=a.length) break;
        		 if(a[ind]<=c) {
        			 ind++;
        			 max+=c;
        		 } else {
        			 break;
        		 }
        	 }
         }

         for(int i=ind; i<a.length;i++) {
        	 max+=a[i];
         }

         System.out.print(max);
     }

     public static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> implements Comparable<Pair<K, V>> {
    		/** serialVersionUID. */
    	    private static final long serialVersionUID = 6411527075103472113L;

    	    public Pair(final K key, final V value) {
    	        super(key, value);
    	    }

    		@Override
    		public int compareTo(Pair<K, V> o) {

    			Comparable key = (Comparable)this.getKey();
    			Comparable key2 = (Comparable)o.getKey();

    			return key.compareTo(key2);
    		}

    	}

     // 文字列として入力を取得
     public static String gs() {
          return scanner.next();
     }

     // intとして入力を取得
     public static int gi() {
          return Integer.parseInt(scanner.next());
     }

     // longとして入力を取得
     public static long gl() {
          return Long.parseLong(scanner.next());
     }

     // doubleとして入力を取得
     public static double gd() {
          return Double.parseDouble(scanner.next());
     }
}