Problem Description

You are given an integer $ N $ and two integer sequences $ A $ and $ B $ of length $ N $.
For the next $ N $ days, the following events will happen to Takahashi:

• Morning of day $ i $: His money increases by $ A_i $ yen.
• Afternoon of day $ i $: He can purchase a computer by paying any amount of money, as long as his money does not become negative. He can also choose not to buy a computer. If he already has a computer and buys a new one, the old one is discarded.
• Evening of day $ i $: He works. To complete this work, Takahashi must have a computer that costs at least $ B_i $ yen.

Initially, Takahashi has 0 yen and does not have a computer.

Determine whether it is possible for Takahashi to complete all the work.
If possible, output the maximum amount of money Takahashi can have at the end of day $ N $ under the condition that he completes all the work.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $\vdots$ $ A_N $ $ B_N $

Output Format

If it is possible for Takahashi to complete all the work, output the maximum amount of money he can have at the end of day $ N $ under the condition that he completes all the work.
If it is impossible for Takahashi to complete all the work, output $ -1 $.

Sample Input and Output

Sample Input #1

3
5 1
2 4
4 6

Sample Output #1

4

Sample Input #2

3
3 2
1 2
3 6

Sample Output #2

-1

Notes/Hints

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq B_i \leq 10^9$
• All inputs are integers.

Sample Explanation 1

Takahashi can purchase a 1 yen computer on the afternoon of day 1, a 6 yen computer on the afternoon of day 2, and choose not to buy a computer on the afternoon of day 3. This way, he can complete all the work and have 4 yen at the end of day 3.

Sample Explanation 2

No matter what choices Takahashi makes, he cannot complete all the work. Therefore, output $ -1 $.

见题面 Input 部分

见题面 Output 部分