Driving Lanes

문제

While driving around a curve on the highway, Sam realizes that if they use the inside lane, they travel a shorter distance. Sam wonders what is the minimum distance needed to travel to the destination.

The multilane highway consists of a sequence of straightaways that are connected by curves. When going around a curve, the distance travelled depends on which lane you are in. Each curve has a curvature $cc$ and stretch $ss$. Specifically, if Sam is in lane $ii$, then they travel $s+c\cdot is\; +\; c\; \backslash cdot\; i$ meters while going around this curve.

Whenever Sam is on a straightaway, they may change from one lane into an adjacent lane.  When changing to an adjacent lane, Sam moves forward $kk$ meters, but travels a total of $k+rk+r$ meters.  Each lane change must be completed before the car reaches the end of the current straightaway.  Sam may change lanes multiple times in the same straightaway. For safety reasons, changing lanes is not possible on curves.

Sam starts in lane $11$ and wishes to end in lane $11$. What is the minimum distance they must travel?

입력

The first line of input contains two integers $nn$ ($1\le n\le 2501\; \backslash leq\; n\; \backslash leq\; 250$), which is the number of straightaways, and $mm$ ($1\le m\le 2501\; \backslash leq\; m\; \backslash leq\; 250$), which is the number of lanes on the highway. The lanes are numbered $1,2,\dots ,m1,\; 2,\; \backslash dots,\; m$.

The second line of input contains two integers $kk$ ($1\le k\le {10}^{6}1\; \backslash leq\; k\; \backslash leq\; 10^6$) and $rr$ ($1\le r\le {10}^{6}1\; \backslash leq\; r\; \backslash leq\; 10^6$), which are the lane changing parameters.

The next $nn$ lines describe the straightaways in order. Each of these lines contains a single integer $\mathrm{\ell }\backslash ell$ ($1\le \mathrm{\ell }\le {10}^{6}1\; \backslash leq\; \backslash ell\; \backslash leq\; 10^6$), which is the length of this straightaway.

The next $n-1n-1$ lines describe the curves in order. Each of these lines contains two integers $ss$ ($1\le s\le {10}^{6}1\; \backslash leq\; s\; \backslash leq\; 10^6$), which is the stretch of this curve, and $cc$ ($-{10}^6\le c\le {10}^6-10^6\; \backslash leq\; c\; \backslash leq\; 10^6$), which is the curvature of this curve. It is guaranteed that $s+c\cdot m>0s\; +\; c\; \backslash cdot\; m\; >\; 0$.

The $ii$th curve connects the $ii$th and $(i+1)(i+1)$th straightaway.

출력

Display the minimum distance Sam must travel.

4 3
5 2
10
10
10
10
4 -1
4 -1
4 1

51

4 3
5 2
10
10
10
10
10 -3
10 -3
10 1

61