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
/*
* @Author Silviase(@silviasetitech)
* For ProCon
*/

import java.util.*;
import java.lang.*;
import java.math.*;
import java.awt.*;

public class Main{

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

        int n = sc.nextInt();
        int m = sc.nextInt();
        int itr = 0;
        int cnt = 0;
        long ans = 0;
        PriorityQueue<Integer> card = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < n; i++) {
            card.add(sc.nextInt());
        }
        Pair[] pair = new Pair[m];
        for (int i = 0; i < m; i++) {
            pair[i] = new Pair(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(pair,Comparator.comparing(v -> -v.y)); // good

        while (cnt < n) {
            if (itr == m || (!card.isEmpty() && card.peek() >= pair[itr].y)) {
                /**
                 * not to change
                 */
                cnt++;
                long tmp = card.poll();
                /*
                System.out.println("tmp:" + tmp);
                */
                ans += tmp;
            }else{
                /**
                 * use Math.min(n-cnt, pair[itr].x) - cards
                 * if n-cnt > pair[itr].x, use all x - cards.
                 */
                int used = Math.min(n-cnt, pair[itr].x);
                cnt += used;
                ans += (long)pair[itr].y*(long)used;
                itr++;
            }
            /*
            System.out.println("Nowans:" + ans);
            */
        }
        System.out.println(ans);

        sc.close();
    }

    /**
     * Pair_int
     */
    public static class Pair {
        public int x;
        public int y;

        /**
         * Constructor 
         * Sample Code
         * 
         *      Pair[] pair = new Pair[5];
                for (int i = 0; i < 5; i++) {
                    pair[i] = new Pair(sc.nextInt(), sc.nextInt());
                }
                for (int i = 0; i < 5; i++) {
                    System.out.println(pair[i].x + " " + pair[i].y);
                }
         *
         */
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public String toString() {
            return "(" + x + ", " + y + ")";
        }


    }
}


