配点 : $600$ 点

問題文

りんごさんはアーチェリーの大会「AtArcher」に出場しました。

AtArcher では、数直線上に表される的に $N$ 本の矢を撃って合計得点を競います。的の中心は座標 $0$ であり、矢が当たった位置に応じて以下のように得点が定められています。

• $i = 0, 1, \dots, M-1$ に対して、中心からの距離が $r_i$ から $r_{i+1}$ までの場所に当てると $s_i$ 点を獲得し、中心からの距離が $r_M$ より大きい場所に当てると $0$ 点を獲得する。境界に当たった場合は高い方の得点になる。
• 中心から近いほど高得点が得られるようになっている。すなわち、次を満たす。- $0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M$
  • $s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0$
• $0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M$
• $s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0$

例えば、$r = (0, 2, 7, 9), s = (100, 70, 30)$ の場合、得点は下図のようになります。

さらに、AtArcher では「どの $2$ 本の矢も距離 $D$ 以上の間隔を空ける」という特殊ルールがあります。これに違反した場合は失格となり、全体の得点が $0$ 点になります。

さて、りんごさんが全ての矢を撃ち終わった時点で、最大何点獲得できるでしょう？

制約

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq D \leq 10^6$
• $0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M \leq 10^{11}$
• $10^{11} \geq s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$ $D$

$r_0$ $r_1$ $\cdots$ $r_{M-1}$ $r_M$

$s_0$ $s_1$ $\cdots$ $s_{M-1}$

出力

答えを出力してください。

3 3 3
0 2 7 9
100 70 30

270

この入力例は問題文中の例に対応していますが、$D = 3$ となっています。

例えば、$N = 3$ 本の矢が座標 $-6, -2, 1$ に当たると、それぞれ $70, 100, 100$ 点を獲得します。このとき合計得点は $270$ 点となり、実現可能なものとしては最大です。

なお、すべての矢を $100$ 点のエリアに当てて $300$ 点を取ることはできません。なぜなら、どの $2$ 本の矢も距離 $D = 3$ 以上の間隔を空けなければ、失格で $0$ 点になるからです。

3 3 8
0 2 7 9
100 70 30

200

この入力例も問題文中の例に対応していますが、$D = 8$ となっています。

例えば、$N = 3$ 本の矢が座標 $-7, 1, 9$ に当たると、それぞれ $70, 100, 30$ 点を獲得します。このとき合計得点は $200$ 点となり、実現可能なものとしては最大です。

7 5 47
0 10 40 100 160 220
50 25 9 6 3

111

例えば、下図のように矢を当てると、合計得点は $111$ 点となり、これが最大です。

100 1 5
0 7
100000000000

300000000000

$N = 100$ 本の矢を当てることができますが、失格にならないためには、得点が入るゾーンに $3$ 本までしか入れることができません。

15 10 85
0 122 244 366 488 610 732 854 976 1098 1220
10 9 8 7 6 5 4 3 2 1

119