Problem D
Skrift

Bjarki writing

Bjarki is going to write an $n$-letter word. Bjarki hasn’t decided what word it will be, but he knows that it will consist of $m$ different letters where the $i$-th letter apppears $a_i$ times in the word and it takes $b_i$ milligrams of eraser to erase an instance of this letter.

Bjarki forgot his eraser at home so now he is in trouble. He asks his friend Unnar to go to A4 to buy an eraser for him. Unnar is so good hearted that he takes him up on it and goes to A4. On the way to A4 Unnar realizes that he has no idea how much Bjarki will erase and is unsure what to do. He decides to first go to Didda the Oracle and ask her.

Didda is a strange woman. She told Unnar that Bjarki’s writing could be described by $Q$ operations where each operation consists of two integers $x_i,y_i$. If $x_i = 1$ it means Bjarki writes $y_i$ letters, but if $x_i = 2$ it means Bjarki erases the last $y_i$ letters. Satisfied with this, Unnar rushes to A4 but then starts thinking: of all the strings that Bjarki could be writing given the content of the $Q$ queries, what’s the maximum amount of eraser he could need?

Now Unnar calls you and passes all this info onto you, asking for help. How many milligrams of eraser should Unnar buy?

Input

The first line of the input contains three integers $1 \le n \le 10^9, 1 \le m,q \le 10^5$. The next $m$ lines contain two integers $1 \le a_i \le n, 1 \le b_i \le 10^4$. The next $q$ lines contain two integers $1 \le x_i \le 2, 1 \le y_i \le n$.

It is guaranteed that the sum of all the $a_i$ will be $n$. Bjarki will never erase more letters than there are in the word. Furthermore Bjarki will never erase more letters than have been written.

Output

Print a single integer, how many milligrams of eraser Unnar should buy to be sure it’ll be enough. The answer will never exceed $10^{18}$.

Scoring

4 2 4
2 4
2 2
1 1
1 2
2 2
1 3

8

3 2 3
1 3
2 2
1 3
2 3
1 3

7