D - AtArcher Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

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

Score : 600 points

Problem Statement

Ringo is participating in an archery contest AtArcher.

In AtArcher, a participant shoots N arrows at a target on a number line to compete for the total score. The center of the target is at coordinate 0. Based on where the arrow hits, the score of the shot is defined as follows.

  • For i = 0, 1, \dots, M-1, if the arrow hits a point whose distance from the center of the target is between r_i and r_{i+1}, the score is s_i. If the distance is greater than r_M, the score is 0. If the arrow hits the boundary, the higher score is applied.
  • The closer to the center, the higher the score is. In other words, the following is satisfied.
    • 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

For example, the figure below shows the score for a shot when r = (0, 2, 7, 9), s = (100, 70, 30).

Additionally, AtArcher has one special rule: the distance between any two arrows must always be at least D. Violating this rule disqualifies the participant, making the total score 0.

What is the maximum total score that Ringo can get from all the shots?

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 3 3
0 2 7 9
100 70 30

Sample Output 1

270

This sample input corresponds to the case in the Problem Statement, with D = 3.

For example, if the N = 3 arrows hit the coordinates -6, -2, 1, they score 70, 100, 100, respectively, for a total score of 270, which is the maximum achievable.

Note that you cannot hit the 100-point area with all the arrows to score 300, because the distance between any two arrows must be at least D = 3, or you will be disqualified and score 0.

Sample Input 2

3 3 8
0 2 7 9
100 70 30

Sample Output 2

200

This sample input corresponds to the case in the Problem Statement, with D = 8.

For example, if the N = 3 arrows hit the coordinates -7, 1, 9, they score 70, 100, 30, respectively, for a total score of 200, which is the maximum achievable.

Sample Input 3

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

Sample Output 3

111

For example, if you shoot the arrows as shown in the following figure, you will score 111 in total, which is the maximum.

Sample Input 4

100 1 5
0 7
100000000000

Sample Output 4

300000000000

You can shoot N = 100 arrows, but in order to avoid disqualification, at most 3 arrows can hit the area with a positive score.

Sample Input 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

Sample Output 5

119