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

见题面

见题面