Double Radars

문제

Ali recently found a treasure and has arranged the coins from the treasure around a circle. There are $kk$ houses around the circle with equal distances. Houses are numbered $11$ through $kk$ consecutively in the clockwise direction. The treasure contains $nn$ coins, where the $ii$^th coin (for $1\le i\le n1\; \backslash le\; i\; \backslash le\; n$) has the value $w_{i}w\_i$ and is located at the house $x_{i}x\_i$.

To protect the treasure, Ali has installed two radars stationed at the center of the circle, monitoring its circumference. Radar $ii$ (for $i\in \{1,2\}i\; \backslash in\; \backslash \{1,\; 2\backslash \}$) starts by monitoring house $r_{i}r\_i$ and moves $\frac{1}{v_i}\backslash frac\{1\}\{v\_i\}$ houses per minute. More intuitively, every $v_{i}v\_i$ minutes, the Radar $ii$ goes one house forward. Initially, the first radar moves clockwise, and the second radar moves counterclockwise. Whenever the two radars meet, they both reverse their directions. Note that this can happen in the area between two adjacent houses.

Gholi, who wants to steal as many coins as possible, plans to start at an arbitrary house on the circle and move at most $\frac{1}{v}\backslash frac\{1\}\{\; v\}$ houses per minute in either direction (clockwise or counterclockwise). He starts moving at the time zero. He can reverse his direction anytime or stay still for a while. If Gholi crosses paths with one of the radars at any moment, he will be immediately caught and sent to jail. He cannot steal a coin if this happens at a house.

Help Gholi to maximize the total value of the coins he can steal before being detected by the radars.

입력

The first line contains three integers, $nn$ ($1\le n\le {10}^{5}1\; \backslash le\; n\; \backslash le\; 10^5$) number of coins, $kk$ ($1\le k\le {10}^{9}1\; \backslash le\; k\; \backslash le\; 10^9$) number of houses around the circle, and $vv$ ($1\le v\le {10}^{4}1\; \backslash le\; v\; \backslash le\; 10^4$) speed of Gholi.

The second line contains the starting monitoring house $r_{1}r\_1$ and speed $v_{1}v\_1$ of the first radar ($1\le r_1\le k1\; \backslash le\; r\_1\; \backslash le\; k$, $1\le v_1\le {10}^{4}1\; \backslash le\; v\_1\; \backslash le\; 10^4$).

The third line contains the starting monitoring house $r_{2}r\_2$ and speed $v_{2}v\_2$ of the second radar ($1\le r_2\le k1\; \backslash le\; r\_2\; \backslash le\; k$, $1\le v_2\le {10}^{4}1\; \backslash le\; v\_2\; \backslash le\; 10^4$). It is guaranteed that $r_1\mathrm{\ne }{r}_{2}r\_1\; \backslash ne\; r\_2$.

The fourth line contains $nn$ distinct integers, $x_1,x_2,\dots ,x_{n}x\_1,\; x\_2,\; \backslash dots\; ,\; x\_n$, representing the houses where the coins are located ($1\le x_i\le k1\; \backslash le\; x\_i\; \backslash le\; k$).

The fifth line contains $nn$ integers, $w_1,w_2,\dots ,w_{n}w\_1,\; w\_2,\; \backslash dots\; ,\; w\_n$, representing the value of each coin ($1\le w_i\le {10}^{9}1\; \backslash le\; w\_i\; \backslash le\; 10^9$).

출력

Output the maximum total value of coins Gholi can steal before being detected by the radars.

3 5 1
1 2
2 3
1 2 4
1 2 4

6