Problems
Bitaro, the brave hero, has set out on an adventure to defeat monsters.
There are N monsters labeled from 1 to N. To defeat the i-th monster, Bitaro must have a strength of at least Aᵢ. Upon defeating the i-th monster, his strength increases by Bᵢ.
Bitaro follows the strategy below to defeat all the monsters:
Start with a specific monster j (1 ≤ j ≤ N) and defeat the monsters in order: j, j+1, …, N.
If j ≥ 2, then proceed to defeat the monsters 1, 2, …, j−1 in sequence.
Given the information about the monsters (arrays A and B), determine the minimum initial strength x that Bitaro needs to defeat all the monsters.
Input
The first line contains an integer N.
The second line contains N space-separated integers A₁, A₂, …, A_N.
The third line contains N space-separated integers B₁, B₂, …, B_N.
[Constrains]
2 ≤ N ≤ 500\ 000 0 ≤ A_i ≤ 10^9 (1 ≤ i ≤ N )0 ≤ B_j ≤ 10^9 (1 ≤ j ≤ N )Given values are all integers.
Output
Print a single integer x, the minimum initial strength required for Bitaro to defeat all the monsters.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 10 | N ≤ 2,000 and the minimum initial strength x is at most 10 |
| #2 | 21 | N ≤ 2,000 |
| #3 | 19 | The minimum initial strength x is at most 10 |
| #4 | 22 | Bᵢ = 1 for all i (1 ≤ i ≤ N) |
| #5 | 28 | No additional constraints |
Example #1
5
1 3 2 8 6
4 3 1 1 2
1
Starting with x = 1 and processing monsters 1 through 5 in order:
Monster 1: 1 ≥ 1, new strength = 1+4 = 5
Monster 2: 5 ≥ 3, new strength = 5+3 = 8
Monster 3: 8 ≥ 2, new strength = 8+1 = 9
Monster 4: 9 ≥ 8, new strength = 9+1 = 10
Monster 5: 10 ≥ 6, new strength = 10+2 = 12
Thus, x = 1 is sufficient.
Example #2
5
1 6 3 3 2
1 2 1 0 1
3
Starting with x = 3 and beginning from monster 3, the sequence of battles ensures that each monster’s requirement is met. Hence, the answer is 3.
Example #3
10
11 9 8 12 7 7 8 12 9 10
1 1 1 1 1 1 1 1 1 1
9
By choosing an appropriate starting monster (e.g., monster 5), x = 9 is sufficient for Bitaro to defeat all monsters.
Example #4
7
1125 638 0 37 737 820 1202
23 984 558 350 52 345 580
0
Starting with x = 0 from monster 3 works since the 3rd monster requires 0 strength. Then, subsequent strength increases allow Bitaro to defeat the remaining monsters.
You must sign in to write code.