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.io.Serializable;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {

	/**
	 * problem solver
	 */
	public static class Problem {

		/**
		 * paramters
		 */
		private int n;
		private int m;
		private ArrayList<Long> a;
		private ArrayList<Long> c;
		private ArrayList<Integer> b;

		/**
		 * constructor
		 */
		Problem() {
			a = new ArrayList<Long>();
			c = new ArrayList<Long>();
			b = new ArrayList<Integer>();
			n = 0;
			m = 0;
		}

		/**
		 * standard input
		 */
		void input() {
			Scanner sc = new Scanner(System.in);
			n = sc.nextInt();
			m = sc.nextInt();

			for (int i = 0; i < n; i++) {
				a.add(sc.nextLong());
			}
			
			for (int i = 0; i < m; i++) {
				b.add(sc.nextInt());
				c.add(sc.nextLong());
			}
			sc.close();
		}


		public static class Bc implements Comparable<Bc>, Serializable {

			private static final long serialVersionUID = 7126883977005996870L;

			public int b;
			public long c;

			Bc(int b, long c) {
				this.b = b;
				this.c = c;
			}

//            @Override
//            public int hashCode() {
//            	return Objects.hash(t,d);
//            }

			@Override
			public boolean equals(Object other) {
				if (other == this) {
					return true;
				}

				if (other instanceof Bc) {
					Bc that = (Bc) other;
					return Objects.equals(that.b, this.b) && Objects.deepEquals(that.c, this.c);
				}
				return false;
			}

			@Override
			public int compareTo(Bc that) {
				Comparator<Long> naturalOrder = Comparator.naturalOrder();
				return Objects.compare(this.c, that.c, naturalOrder);
			}

			@Override
			public String toString() {
				Object[] params = { b, c };
				MessageFormat mf = new MessageFormat("({0},{1})");
				return mf.format(params);
			}
		}
		

		/**
		 * solver
		 */
		void solve() {
			PriorityQueue<Long> pque = new PriorityQueue<>();
			ArrayList<Bc> bcs = new ArrayList<>();
			ArrayList<Long> candidates = new ArrayList<>();

			for (Long e : a) {
				pque.add(e);
			}
			
			for (int i =0; i < m;i++) {
				Bc bc = new Bc(b.get(i), c.get(i));
				bcs.add(bc);				
			}
			
			Collections.sort(bcs, Collections.reverseOrder());
			
			
			for(Bc bc : bcs) {
				for(int i=0;i<bc.b;i++) {
					candidates.add(bc.c);
					
					if(candidates.size() == n) {
						break;
					}
				}
				if (candidates.size() == n) {
					break;
				}
			}

			for(long l: candidates) {
				long amin = pque.peek();
				if (amin < l) {
					pque.poll();
					pque.add(l);
				}
			}
			
			
			long ans = 0;
			for (long e: pque) {
				ans += e;
			}
			
			System.out.println(ans);

		}

	}

	public static void main(String args[]) {

		Problem p = new Problem();

		p.input();

		p.solve();
	}
}
