题目描述

りんごさんはアーチェリーの大会「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$ 点になります。

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

输入格式

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

$N$ $M$ $D$ $r_0$ $r_1$ $\cdots$ $r_{M-1}$ $r_M$ $s_0$ $s_1$ $\cdots$ $s_{M-1}$

输出格式

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

题目大意

数轴上有一个箭靶以 $0$ 为轴心左右对称，给定每个得分区域的范围和分值，要求射 $N$ 支箭在靶上，且任意两支箭的距离不少于 $D$，求最大得分。保证从中心向两侧分数不增。特别的，如果有一只箭射在了分界点上，以较大得分为准。

3 3 3
0 2 7 9
100 70 30

270

3 3 8
0 2 7 9
100 70 30

200

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

111

100 1 5
0 7
100000000000

300000000000

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

提示

制約

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

Sample Explanation 1

この入力例は問題文中の例に対応していますが、$D\ =\ 3$ となっています。 例えば、$N\ =\ 3$ 本の矢が座標 $-6,\ -2,\ 1$ に当たると、それぞれ $70,\ 100,\ 100$ 点を獲得します。このとき合計得点は $270$ 点となり、実現可能なものとしては最大です。  なお、すべての矢を $100$ 点のエリアに当てて $300$ 点を取ることはできません。なぜなら、どの $2$ 本の矢も距離 $D\ =\ 3$ 以上の間隔を空けなければ、失格で $0$ 点になるからです。

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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