← 返回题目列表

AtCoder · nadafes2022_day2_k

K. 展览3

中文机器翻译题面 查看原题

配点 : 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