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 Pair{
 public long a;
 public long b;
 Pair(long a,long b){
 this.a=a;
 this.b=b;
 }
 public String toString(){
	 return this.a+"::"+this.b;
 }
}
public class Main{
	public static void main(String arg[]){
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
	    long b=sc.nextLong();
	    long arr[]=new long[a];
		for(int i=0;i<a;i++)
			arr[i]=sc.nextLong();
		Arrays.sort(arr);
		ArrayList<Pair> al=new ArrayList<>();
		for(int i=0;i<b;i++)
			al.add(new Pair(sc.nextLong(),sc.nextLong()));
	     Collections.sort(al,new Comparator<Pair>(){
			 @Override
			public int compare(Pair a,Pair b){
				if(a.b==b.b)
					return (int)(b.a-a.a);
					else return (int)(b.b-a.b);
			}
		}
		);
		int k=0;
		for(int i=0;i<b;i++){
			for(int j=0;j<al.get(i).a;j++){
				if(k<a&&al.get(i).b>arr[k])
				{
					arr[k]=al.get(i).b;
					k++;
				}
				else break;
			}
			if(k >= a || al.get(i).b<arr[k])
				break;
		}
		long s=0;
		for(int i=0;i<a;i++){
			s+=arr[i];
		}
			System.out.println(s);
	}
}