AT_joig2026final_c ケーキの飾りつけ (Cake 4)

JOI 君和 IOI 酱是一对兄妹，今天是 IOI 酱的生日。为了庆祝，JOI 君购买了 $N$ 个蛋糕。每个蛋糕都编号为 $1$ 到 $N$，第 $i$ 个蛋糕的大小为 $A_i$。JOI 君为了让 IOI 酱高兴，想出了 $N$ 个方案。第 $i$ 个方案是给蛋糕 $i$ 装饰一个甜度为 $V_i$ 的草莓。 由于 JOI 君也很注重蛋糕的外观，需要选择 $0$ 个或多个方案，使得以下条件全部满足： - 对于装饰了草莓的**任意不同的两块蛋糕**，这两块蛋糕的大小之和不等于 $S$。 - 对于装饰了草莓的**任意不同的两块蛋糕**，这两块蛋糕的大小之差不等于 $D$。 请注意，如果选择的装饰方案个数不超过 $1$，上述条件总是被满足。 IOI 酱喜欢吃甜食，希望装饰的草莓甜度总和尽可能大。如果一个草莓都没有被装饰，则甜度总和为 $0$。 现在给定蛋糕和草莓的信息，请编写程序，求装饰的草莓甜度总和的最大可能值。 ---

输入通过标准输入按以下格式给出。 > $N$ $S$ $D$ > $A_1$ $A_2$ $\cdots$ $A_N$ > $V_1$ $V_2$ $\cdots$ $V_N$

输出仅一行，表示最大可能的草莓甜度总和。 ---

## 小题 1.（$7$ 分）$N \leq 20$。 2.（$14$ 分）$S \leq 40$，$D \leq 20$，$A_i \leq 20$（$1 \leq i \leq N$）。 3.（$18$ 分）$S = 1$。 4.（$30$ 分）$D = 1$，$S$ 为奇数。 5.（$15$ 分）$D = 1$。 6.（$16$ 分）无附加约束。 --- ## 样例解释 1 考虑选择并执行方案 $2,3,4$。无论从装饰了草莓的蛋糕 $2,3,4$ 任意选择两块，其大小和都不会等于 $8$，其大小差也不会等于 $3$。因此，这些方案可以全部执行。此时，草莓的甜度总和为 $6+7+5=18$。 不存在草莓甜度总和大于 $18$ 的其他选择方式，所以输出 $18$。 该输入满足小题 $1,2,6$ 的约束。 --- ## 样例解释 2 该输入满足小题 $1,2,3,6$ 的约束。 --- ## 样例解释 3 该输入满足所有小题的约束。 # 数据范围 - $1 \leq N \leq 200\,000$。 - $1 \leq S \leq 10^9$。 - $1 \leq D \leq 10^9$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq V_i \leq 10^9$（$1 \leq i \leq N$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译