配点 : 700 点
問題文
在NPCA博物馆,有一条从东到西笔直的走廊。 N 显示照片。图片 i (1\leq i\leq N) 来自走廊西端 X_i 显示在仪表位置,其值为 V_i 。
PCT 总监必须满足以下条件。 删除 N-M 图片,M 我决定只保留一张照片。
- 哪个 2 对于每张图片,位置是 距离超过 D 米。
求剩余画作的值的最大总和。
制約
- 1 \leq M \leq N \leq 3\times 10^5
- 1 \leq D \leq 10^9
- 0 \leq X_1 < X_2 < \ldots < X_N \leq 10^9
- |V_i| \leq 10^9
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M D X_1 X_2 \ldots X_N V_1 V_2 \ldots V_N
出力
输出剩余画作总价值的最大值。但如果无法满足条件去除画作,
输出impossible 。
入力例 1
4 2 3 0 2 4 5 5 1 -4 3
出力例 1
8
絵 2 和图片 最好删除 3 。 有
入力例 2
4 3 2 0 1 2 3 1 1 1 1
出力例 2
impossible
入力例 3
5 2 4 0 3 5 6 9 -4 -8 3 -10 -6
出力例 3
-1