配点: $100$ 点

问题文

吉加君要参加名为“GigaCode 20XX”的活动，为此他决定用零花钱买一台电脑。如果以今天作为第一天，他必须在第 $D$ 天购买电脑。

在第一天的早上，他手头的零花钱为0日元。而在第 $i$ 天的中午，他将获得 $a_i$ 日元的零花钱。

现在，电脑的价格每天都在变动。第 $i$ 天的电脑价格为 $b_i$ 日元，这个价格在当天的0时到24时不会变化。

给定 $D$ 天的零花钱信息和电脑价格信息，求他可以买到的电脑价格的最小值。如果他无法在第 $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 分) 没有额外的约束。

输入

输入以以下格式从标准输入中给出。

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

输出

请输出吉加君能够购买的电脑价格的最小值。如果他无法在第 $D$ 天之前购买电脑，则输出 -1。

输入示例 1

1
120000
100000

输出示例 1

100000

因为在第一天晚上他手头有120,000日元，所以他可以在第一天晚上买一台价值100,000日元的电脑。因此，正确答案是100000。

注意，这个示例符合子任务1和子任务2的约束条件。

输入示例 2

1
70000
100000

输出示例 2

-1

他在第一天晚上手头有70,000日元，但是电脑需要100,000日元，所以他无法购买电脑。因此，正确答案是-1。

输入示例 3

5
10000 10000 10000 10000 10000
41210 27556 29018 42919 33762

输出示例 3

29018

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

• 手头现金：10,000日元
• 电脑价格：41,210日元 → 无法购买

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

• 手头现金：10,000 + 10,000 + 10,000 = 30,000日元
• 电脑价格：29,018日元 → 可以购买

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

• 手头现金：10,000 + 10,000 + 10,000 + 10,000 + 10,000 = 50,000日元
• 电脑价格：33,762日元 → 可以购买

此外，他无法在第二天和第四天晚上购买电脑。因此，答案是29,018日元。

注意，这个示例符合子任务2的约束条件。

输入示例 4

5
10000 10000 10000 10000 10000
30000 29999 29998 29997 29996

输出示例 4

29996