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.util.Arrays;
import java.util.Comparator;

public class Main
{
  static long y[];
  static int n;
  static int m;
  public static void main(String[] args) throws IOException
  {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in), 1);
    String sl[];


    sl = r.readLine().split(" ");
    n = Integer.parseInt(sl[0]);
    m = Integer.parseInt(sl[1]);

    Integer v[] = new Integer[n + m];
    y = new long[n + m];

    long a[] = new long[n];
    int b[] = new int[m];
    long c[] = new long[m];

    sl = r.readLine().split(" ");
    for(int i = 0; i < n; i++)
    {
      v[i] = i;
      a[i] = Long.parseLong(sl[i]);
      y[i] = a[i];
    }

    for(int i = 0; i < m; i++)
    {
      sl = r.readLine().split(" ");
      b[i] = Integer.parseInt(sl[0]);
      c[i] = Integer.parseInt(sl[1]);
      v[i + n] = i + n;
      y[i + n] = c[i];
    }

    class Comp implements Comparator<Integer>
    {
      @Override
      public int compare(Integer o1, Integer o2)
      {
        if(y[o1] > y[o2])
          return -1;
        else if(y[o1] < y[o2])
          return 1;
        return 0;
      }
    }

    Arrays.sort(v, new Comp());

    long cc = 0;
    int pp = -1;
    int vv = 0;
    int dd = 0;
    while(dd < n)
    {
      if(vv == 0)
      {
        pp++;
        if(v[pp] < n)
        {
          vv = 1;
        }
        else
        {
          vv = b[v[pp] - n];
        }
      }
      
      dd++;
      vv--;
      cc += y[v[pp]];
    }
    
    System.out.println(cc);
    
  }

}