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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {
	static class Pair implements Comparable<Pair> {
		int B;
		long C;

		Pair(int B, long C) {
			this.B = B;
			this.C = C;
		}

		@Override
		public int compareTo(Pair o) {
			if (this.C < o.C) {
				return 1;
			} else if (this.C > o.C) {
				return -1;
			} else {
				return 0;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int M = Integer.parseInt(tokens[1]);
		Long[] A = new Long[N];
		tokens = in.readLine().split(" ");
		for (int i = 0; i < N; ++i) {
			A[i] = Long.parseLong(tokens[i]);
		}
		Arrays.sort(A);

		Queue<Pair> pairs = new PriorityQueue<>();

		for (int i = 0; i < M; ++i) {
			tokens = in.readLine().split(" ");
			int B = Integer.parseInt(tokens[0]);
			long C = Integer.parseInt(tokens[1]);
			pairs.add(new Pair(B, C));
		}

		int index = 0;
		while (index < N) {
			Pair pair = pairs.poll();
			if (pair == null) {
				break;
			}
			for (int i = index; i < Math.min(index + pair.B, N); ++i) {
				if (A[i] >= pair.C) {
					break;
				}
				A[i] = pair.C;
			}
			index += pair.B;
		}

		long result = 0;
		for (int i = 0; i < N; ++i) {
			// System.out.println(" " + A[i]);
			result += A[i];
		}
		System.out.println(result);

		in.close();
	}

	static void step(Queue<Long> queue, int B, long C) {
		int count = 0;
		for (int i = 0; i < B; ++i) {
			long elem = queue.peek();
			if (elem > C) {
				break;
			}
			queue.poll();
			++count;
		}
		for (int i = 0; i < count; ++i) {
			queue.add(C);
		}
		return;
	}
}