配点: 100 点
問題文
Giga君决定用自己的零用钱购买一台电脑,以参加名为“GigaCode 20XX”的活动。今天 1 如果是这一天,他就是 D 您必须在该日期之前购买计算机。
1 第一天早上,他的零花钱是 0 这是日元。另外,i 当天中午零用钱 a_i 日元给了他。
现在,电脑的价格每天都在变化。i 当天电脑价格为 b_i 日元,当日0:00至24:00此价格不变。
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
- 所有输入均为整数
部分点
该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (20 点) D = 1 很满意。
- (40 点) D \leq 365 很满意。
- (40 分) 没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
D a_1 a_2 a_3 ... a_D b_1 b_2 b_3 ... b_D
出力
请输出Giga君可以购买的电脑的最低价格。
但是,如果他使用计算机
请输出 D 如果您无法通过
请输出 -1 。
入力例 1
1 120000 100000
出力例 1
100000
他是 1 截至当天晚上 120 \ 000 因为我有日元,1 当天晚上 100 \ 000 您可以用日元购买一台计算机。
因此,
正确答案是输出100000 。
此输入/输出示例基于子任务 1 约束,小任务 它满足 2 约束。
入力例 2
1 70000 100000
出力例 2
-1
他是 1 截至当天晚上 70 \ 000 我有日元,但我需要买一台电脑。 100 \ 000 他无法购买电脑,因为它需要日元。
正确答案是输出
因此,
正确答案是输出-1 。
入力例 3
5 10000 10000 10000 10000 10000 41210 27556 29018 42919 33762
出力例 3
29018
他 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 约束。
入力例 4
5 10000 10000 10000 10000 10000 30000 29999 29998 29997 29996
出力例 4
29996