AT_gigacode_2019_c.パソコンの購入

Giga 君为了参加“GigaCode 20XX”活动，决定用自己的零花钱购买一台电脑。假设今天是第 $1$ 天，他必须在第 $D$ 天之前买到电脑。

在第 $1$ 天早上，他的零花钱为 $0$ 日元。此外，在第 $i$ 天中午，他会收到 $a_i$ 日元的零花钱。

电脑的价格每天都会变化。第 $i$ 天电脑的价格为 $b_i$ 日元，这个价格在当天的 0 点到 24 点之间保持不变。

现在给出 $D$ 天的零花钱信息和电脑价格信息，请你求出他能够买到的电脑的最低价格。如果他在第 $D$ 天之前无法买到电脑，则输出 -1。另外，他只能使用给定的零花钱，不能使用其他的钱。

输入通过标准输入按以下格式给出：

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

输出 Giga 君能够买到的电脑的最低价格。如果他在第 $D$ 天之前无法买到电脑，则输出 -1。

约束条件

• $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$
• 所有输入均为整数

部分分

本题分为若干小题，若某一小题的所有测试点均通过，则视为该小题通过。
提交代码的得分为通过的小题分数之和。

1. (20 分) 满足 $D = 1$。
2. (40 分) 满足 $D \leq 365$。
3. (40 分) 无额外约束。

样例解释 1

他在第 $1$ 天晚上拥有 $120\,000$ 日元，因此可以在第 $1$ 天晚上以 $100\,000$ 日元购买电脑。所以输出应为 100000。该样例满足小题 1 和小题 2 的约束。

样例解释 2

他在第 $1$ 天晚上拥有 $70\,000$ 日元，但电脑价格为 $100\,000$ 日元，因此无法购买电脑。输出应为 -1。

样例解释 3

如果他在第 $1$ 天晚上尝试购买电脑：

• 所持金额：$10\,000$ 日元
• 电脑价格：$41\,210$ 日元 → 无法购买

如果他在第 $3$ 天晚上尝试购买电脑：

• 所持金额：$10\,000 + 10\,000 + 10\,000 = 30\,000$ 日元
• 电脑价格：$29\,018$ 日元 → 可以购买

如果他在第 $5$ 天晚上尝试购买电脑：

• 所持金额：$10\,000 + 10\,000 + 10\,000 + 10\,000 + 10\,000 = 50\,000$ 日元
• 电脑价格：$33\,762$ 日元 → 可以购买

此外，他在第 $2$、$4$ 天晚上无法购买电脑。因此答案为 $29\,018$ 日元。该样例满足小题 2 的约束。

由 ChatGPT 4.1 翻译