問題文

りんごさんはアーチェリーの大会「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$

例えば、$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}$

出力

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

---

入力例 1

3 3 3
0 2 7 9
100 70 30

出力例 1

270

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

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

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

---

入力例 2

3 3 8
0 2 7 9
100 70 30

出力例 2

200

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

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

---

入力例 3

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

出力例 3

111

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

---

入力例 4

100 1 5
0 7
100000000000

出力例 4

300000000000

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

---

入力例 5

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

出力例 5

119