問題文

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
• 入力はすべて整数

入力例 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