주행 차선

고속도로의 곡선 구간을 주행하던 Sam은 안쪽 차선을 이용하면 더 짧은 거리를 이동한다는 것을 깨닫는다. Sam은 목적지까지 이동하는 데 필요한 최소 거리가 얼마인지 궁금해한다.

다차선 고속도로는 곡선 구간으로 연결된 일련의 직선 구간으로 이루어져 있다. 곡선 구간을 지날 때 이동하는 거리는 어느 차선에 있는지에 따라 달라진다. 각 곡선 구간에는 곡률 $c$와 길이 매개변수 $s$가 있다. 구체적으로 Sam이 차선 $i$에 있다면, 이 곡선 구간을 지나는 동안 $s + c \cdot i$미터를 이동한다.

Sam이 직선 구간에 있을 때는 인접한 차선으로 차선을 변경할 수 있다. 인접한 차선으로 변경할 때 Sam은 앞으로 $k$미터 전진하지만, 총 $k+r$미터를 이동한다. 각 차선 변경은 자동차가 현재 직선 구간의 끝에 도달하기 전에 완료되어야 한다. Sam은 같은 직선 구간에서 여러 번 차선을 변경할 수 있다. 안전상의 이유로 곡선 구간에서는 차선을 변경할 수 없다.

Sam은 차선 $1$에서 출발하여 차선 $1$에서 끝내고자 한다. Sam이 이동해야 하는 최소 거리는 얼마인가?

입력의 첫째 줄에는 직선 구간의 수를 나타내는 정수 $n$ ($1 \leq n \leq 250$)와 고속도로의 차선 수를 나타내는 정수 $m$ ($1 \leq m \leq 250$)가 주어진다. 차선에는 $1, 2, \dots, m$의 번호가 매겨져 있다.

입력의 둘째 줄에는 차선 변경 매개변수인 두 정수 $k$ ($1 \leq k \leq 10^6$)와 $r$ ($1 \leq r \leq 10^6$)가 주어진다.

다음 $n$개의 줄에는 직선 구간이 순서대로 주어진다. 각 줄에는 해당 직선 구간의 길이인 정수 $\ell$ ($1 \leq \ell \leq 10^6$) 하나가 주어진다.

다음 $n-1$개의 줄에는 곡선 구간이 순서대로 주어진다. 각 줄에는 해당 곡선 구간의 길이 매개변수인 정수 $s$ ($1 \leq s \leq 10^6$)와 해당 곡선 구간의 곡률인 정수 $c$ ($-10^6 \leq c \leq 10^6$)가 주어진다. $s + c \cdot m > 0$임이 보장된다.

$i$번째 곡선 구간은 $i$번째 직선 구간과 $(i+1)$번째 직선 구간을 연결한다.

Sam이 이동해야 하는 최소 거리를 출력한다.