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.