2025-ho-t2_Bitaro_the_Brave_2 (JOI JOI)
Time limit: 1 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: greedy, prefix sum, mathematics

![](_page_0_Picture_0.jpeg)

# Bitaro the Brave 2

Bitaro, the brave hero, has set out on an adventure to defeat monsters.

Bitaro has a strength value, denoted as *x*, which starts at an initial value. There are *N* monsters, each labeled with a number from 1 to *N*. To defeat the *i*-th monster (1 ≤ *i* ≤ *N*), Bitaro must have a strength of at least *A<sub>i</sub>*. Defeating the *i*-th monster increases Bitaro's strength by *B<sub>i</sub>*.

Bitaro wants to defeat all the monsters using the following strategy:

*   Start with a specific monster *j* (1 ≤ *j* ≤ *N*) and defeat the monsters in order: *j*, *j* + 1, ..., *N*.
*   If *j* ≥ 2, go back and defeat the monsters 1, 2, ..., *j* - 1 in sequence.

Given the information about the monsters, write a program to determine the minimum initial strength *x* required for Bitaro to defeat all the monsters.

## Input

Read the following data from the standard input.

```
N
A1 A2 ... AN
B1 B2 ... BN
```

## Output

Output a single integer, the minimum initial strength *x* required for Bitaro to defeat all the monsters.

## Constraints

*   2 ≤ *N* ≤ 500 000.
*   0 ≤ *A<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   0 ≤ *B<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   Given values are all integers.

![](_page_1_Picture_0.jpeg)

## Subtasks

1.  (10 points) *N* ≤ 2,000, and the minimum initial strength *x* is 10 or less.
2.  (21 points) *N* ≤ 2,000.
3.  (19 points) The minimum initial strength *x* is 10 or less.
4.  (22 points) *B<sub>i</sub>* = 1 (1 ≤ *i* ≤ *N*).
5.  (28 points) No additional constraints.

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 5              | 1              |
| 1 3 2 8 6      |                |
| 4 3 1 1 2      |                |

*   Start with an initial strength of 1.
*   Defeat monsters in the following order:
    *   1. Defeat monster 1. Strength increases by 4 to 5.
    *   2. Defeat monster 2. Strength increases by 3 to 8.
    *   3. Defeat monster 3. Strength increases by 1 to 9.
    *   4. Defeat monster 4. Strength increases by 1 to 10.
    *   5. Defeat monster 5. Strength increases by 2 to 12.

This sample input satisfies the constraints of Subtasks 1, 2, 3 and 5.

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 5              | 3              |
| 1 6 3 3 2      |                |
| 1 2 1 0 1      |                |

*   Start with an initial strength of 3.
*   Defeat monsters in the following order:
    *   1. Defeat monster 3. Strength increases by 1 to 4.

![](_page_2_Picture_0.jpeg)

*   2. Defeat monster 4. Strength increases by 0 to 4.
*   3. Defeat monster 5. Strength increases by 1 to 5.
*   4. Defeat monster 1. Strength increases by 1 to 6.
*   5. Defeat monster 2. Strength increases by 2 to 8.

This sample input satisfies the constraints of Subtasks 1, 2, 3 and 5.

| Sample Input 3           | Sample Output 3 |
| :----------------------- | :------------- |
| 10                       | 9              |
| 11 9 8 12 7 7 8 12 9 10 |                |
| 1 1 1 1 1 1 1 1 1 1      |                |

This sample input satisfies the constraints of all the subtasks.

| Sample Input 4              | Sample Output 4 |
| :-------------------------- | :------------- |
| 7                           | 0              |
| 1125 638 0 37 737 820 1202 |                |
| 23 984 558 350 52 345 580   |                |

This sample input satisfies the constraints of Subtasks 1, 2, 3 and 5.

Starter code:

Grader code:

Setup script:

Evaluation script: