Chisaki and Picnic

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

inputFormat

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.

outputFormat

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

样例

3 1
10 1
20 2
30 3
20 2

4