Problem Description

Giga-kun decided to purchase a computer from his allowance to participate in an event called "GigaCode 20XX". Assuming today is day 1, he must buy the computer by day $D$.

At the beginning of day 1, the amount of allowance he has is 0 yen. Also, he receives an allowance of $a_i$ yen at noon on day $i$.

The price of the computer fluctuates daily. The price of the computer on day $i$ is $b_i$ yen, and this price remains unchanged from 0:00 to 24:00 on that day.

Given the information about the allowance and the computer prices for $D$ days, find the minimum possible price of the computer that he can afford. If he cannot buy a computer by day $D$, output -1. Note that he can only use the given allowance and no other money.

Input Format

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

$ D $ $ a_1 $ $ a_2 $ $ a_3 $ ... $ a_D $ $ b_1 $ $ b_2 $ $ b_3 $ ... $ b_D $

Output Format

Output the minimum possible price of the computer that Giga-kun can afford. If he cannot buy a computer by day $D$, output -1.

Sample Input and Output

Sample Input #1

1
120000
100000

Sample Output #1

100000

Sample Input #2

1
70000
100000

Sample Output #2

-1

Sample Input #3

5
10000 10000 10000 10000 10000
41210 27556 29018 42919 33762

Sample Output #3

29018

Sample Input #4

5
10000 10000 10000 10000 10000
30000 29999 29998 29997 29996

Sample Output #4

29996

Notes/Hints

Constraints

• $1 \leq D \leq 200,000$
• $1 \leq a_1, a_2, a_3, \dots, a_D \leq 200,000$
• $1 \leq b_1, b_2, b_3, \dots, b_D \leq 2,000,000,000$
• All inputs are integers

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases in that sub-task. The score of your submitted source code is the sum of the points of the sub-tasks you solved.

1. (20 points) $ D = 1 $
2. (40 points) $D \leq 365$
3. (40 points) No additional constraints

Sample Explanation 1

He has 120,000 yen at the end of day 1, so he can buy the 100,000 yen computer on day 1. Therefore, the correct output is 100000. Note that this input example satisfies the constraints of sub-task 1 and sub-task 2.

Sample Explanation 2

He has 70,000 yen at the end of day 1, but the computer costs 100,000 yen, so he cannot buy the computer. Therefore, the correct output is -1.

Sample Explanation 3

If he tries to buy the computer at the end of day 1:
- Money: 10,000 yen
- Computer price: 41,210 yen → Cannot buy

If he tries to buy the computer at the end of day 3:
- Money: 10,000 + 10,000 + 10,000 = 30,000 yen
- Computer price: 29,018 yen → Can buy

If he tries to buy the computer at the end of day 5:
- Money: 10,000 + 10,000 + 10,000 + 10,000 + 10,000 = 50,000 yen
- Computer price: 33,762 yen → Can buy

Also, he cannot buy the computer at the end of days 2 and 4. Therefore, the answer is 29,018 yen. Note that this input example satisfies the constraints of sub-task 2.

见题面 Input 部分

见题面 Output 部分