配点 : 100 点
問題文
JOI君和IOI酱是兄妹,今天是IOI酱的生日。 JOI君为IOI酱庆祝生日 我购买了 N 蛋糕。为了蛋糕 蛋糕编号为 1 假设一直下雨,直到 N 。 i (1 \leqq i \leqq N) 的大小是 A_i 。 JOI君想要取悦IOI酱, 我制定了N 计划。i 番目 (1 \leqq i \leqq N) 计划很简单 i 甜蜜 V_i 草莓 1 是装饰个人。
JOI君对蛋糕的外观很讲究,所以我们确保满足以下所有条件。 选择并执行至少 0 计划。
- 用草莓装饰不同 2 对于两个蛋糕,它们的大小之和为 这不是 S 。
- 用草莓装饰不同 2 对于两个蛋糕,它们之间的大小差异为 D 。
要执行的计划数量为 1 请注意,当小于或等于 1 时,始终满足条件。
由于IOI喜欢甜的东西,我们希望尽可能增加装饰草莓的总甜度。在这里,1 如果不装饰草莓,则装饰草莓的总甜度为 0 。
给定有关蛋糕和草莓的信息,编写一个程序,找出装饰草莓的最大可能甜度总和。
入力
输入是按以下格式从标准输入给出的。
N S D A_1 A_2 \cdots A_N V_1 V_2 \cdots V_N
出力
装饰草莓的最大可能甜度总和被写入标准输出。 1 行。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq S \leqq 10^9.
- 1 \leqq D \leqq 10^9.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq V_i \leqq 10^9 (1 \leqq i \leqq N).
- 所有输入值均为整数。
小課題
- (7 点) N \leqq 20.
- (14 点) S \leqq 40,D \leqq 20,A_i \leqq 20 (1 \leqq i \leqq N).
- (18 点) S = 1.
- (30 点) D = 1,S 是奇数。
- (15 点) D = 1.
- (16 点)没有额外的限制。 考虑选择
入力例 1
5 8 3 3 4 5 6 7 10 6 7 5 4
出力例 1
18
計画 2,3,4 并执行它。 用草莓装饰的蛋糕 与 2,3,4 有何不同 2 即使您选择其中一个,尺寸之和也是 8 区别在于 3 永远不会发生。 因此,这些计划是可行的。 这里,装饰草莓的总甜度是 6 + 7 + 5 = 18 变为。
总甜度为 18 由于无法选择大于18 。
此输入示例是一个小作业。 1,2,6 满足约束。
入力例 2
3 1 3 4 7 10 3 10 8
出力例 2
11
此输入示例是一个小作业。 1,2,3,6 满足约束。
入力例 3
10 1 1 1 2 3 4 5 6 7 8 9 10 3 1 4 1 5 9 2 6 5 3
出力例 3
25
此输入示例满足所有子任务约束。