O: Chisaki and Picnic

Chisaki, a kindergarten student, decided to bring sweets for the excursion.

There are $ N $ of sweets, and the $ i $ th sweet is priced at $ A_i $ yen and tastes $ B_i $.

Chisaki has $ M $ friends, and the $ j $ th friend cries when she has $ D_j $ or more of sweets priced at $ C_j $ or more.

Chisaki-chan will be happy if her friends cry, so I'd like to bring some sweets so that it doesn't happen.

Help Chisaki-chan to find out how much the total deliciousness of sweets can be.

input

On the first line, the number of sweets $ N $ and the number of friends $ M $ are given, separated by blanks.

Of the following $ N $ lines, $ A_i and B_i $ are given on the $ i $ line, separated by blanks.

Of the following $ M $ lines, $ C_j and D_j $ are given on the $ j $ line, separated by blanks.

output

When you choose a candy to bring so that no friend will cry, output the maximum possible value as the total taste.

Constraint

* $ N, M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 100 \ 000 $
* $ A_1, A_2, A_3, \ dots, A_N $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* $ B_1, B_2, B_3, \ dots, B_N $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* Satisfy $ A_1 \ leq A_2 \ leq A_3 \ leq \ cdots \ leq A_N $
* $ C_1, C_2, C_3, \ dots, C_M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* $ D_1, D_2, D_3, \ dots, D_M $ are integers greater than or equal to $ 1 $ and less than or equal to $ 1 \ 000 \ 000 \ 000 $
* Satisfy $ C_1 \ leq C_2 \ leq C_3 \ leq \ cdots \ leq C_M $



Input example 1


3 1
10 1
20 2
30 3
20 2


Output example 1


Four


Bringing the $ 1 and 3 $ sweets will maximize the total deliciousness of the sweets you bring, as long as you don't make your friends cry.

If you bring both the $ 2 and 3 $ sweets, your friends will cry because you will be "bringing $ 2 $ or more of sweets that cost $ 20 $ or more".

Input example 2


5 3
10 1
20 4
30 5
40 2
50 3
20 3
30 4
40 2


Output example 2


Ten


By bringing the $ 1, 2, and 3 $ sweets, you can maximize the total deliciousness of the sweets you bring, under conditions that will not make any friends cry.





Example

Input

3 1
10 1
20 2
30 3
20 2


Output

4
import java.util.*;

public class Main {
    static HashMap<Integer, HashMap<Integer, Long>> dp = new HashMap<>();
     public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Snack[] snacks = new Snack[n];
        for (int i = 0; i < n; i++) {
            snacks[i] = new Snack(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(snacks, new Comparator<Snack>() {
            public int compare(Snack s1, Snack s2) {
                return s2.price - s1.price;
            }
        });
        Friend[] friends = new Friend[m];
        for (int i = 0; i < m; i++) {
            friends[i] = new Friend(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(friends);
        PriorityQueue<Snack> queue = new PriorityQueue<Snack>(new Comparator<Snack>() {
            public int compare(Snack s1, Snack s2) {
                return s1.value - s2.value;
            }
        });
        int idx = 0;
        for (int i = 0; i < m; i++) {
            while (idx < n && friends[i].price <= snacks[idx].price) {
                queue.add(snacks[idx]);
                idx++;
            }
            while (friends[i].count <= queue.size()) {
                queue.poll();
            }
        }
        while (idx < n) {
            queue.add(snacks[idx]);
            idx++;
        }
        long total = 0;
        while (queue.size() > 0) {
            total += queue.poll().value;
        }
        System.out.println(total);
    }
    
    static class Snack {
        int price;
        int value;
        
        public Snack(int price, int value) {
            this.price = price;
            this.value = value;
        }
        
        public String toString() {
            return "price:" + price + " value:" + value;
        }
    }
    
    static class Friend implements Comparable<Friend> {
        int price;
        int count;
        
        public Friend(int price, int count) {
            this.price = price;
            this.count = count;
        }
        
        public int compareTo(Friend another) {
            return another.price - price;
        }
    }
}
