AT_joi2025ho_b 勇者ビ太郎 2 (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 \leq i \leq N $ ), Bitaro must have a strength of at least $ A_i $ . Defeating the $ i $ -th monster increases Bitaro's strength by $ B_i $ . Bitaro wants to defeat all the monsters using the following strategy: 1. Start with a specific monster $ j $ ( $ 1 \leq j \leq N $ ) and defeat the monsters in order: $ j, j + 1, \ldots, N $ . 2. If $ j \geq 2 $ , go back and defeat the monsters $ 1, 2, \ldots, 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. ---

Read the following data from the standard input. > $ N $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ B_1 $ $ B_2 $ $ \dots $ $ B_N $

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

### Subtasks 1. ( $ 10 $ points) $ N \leq 2\,000 $ , and the minimum initial strength $ x $ is $ 10 $ or less. 2. ( $ 21 $ points) $ N \leq 2\,000 $ . 3. ( $ 19 $ points) The minimum initial strength $ x $ is $ 10 $ or less. 4. ( $ 22 $ points) $ B_i = 1 $ ( $ 1 \leq i \leq N $ ). 5. ( $ 28 $ points) No additional constraints. --- ### Sample Explanation 1 - 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 Explanation 2 - Start with an initial strength of $ 3 $ . - Defeat monsters in the following order: 1. Defeat monster $ 3 $ . Strength increases by $ 1 $ to $ 4 $ . 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 Explanation 3 This sample input satisfies the constraints of all the subtasks. --- ### Sample Explanation 4 This sample input satisfies the constraints of Subtasks $ 1,2,3 $ and $ 5 $ . ### Constraints - $ 2 \leq N \leq 500\,000 $ . - $ 0 \leq A_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ). - $ 0 \leq B_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ). - Given values are all integers.