차선 주행

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

여러 차선이 있는 고속도로는 직선 구간들이 곡선으로 연결된 형태이다. 곡선을 돌 때 이동하는 거리는 어느 차선에 있느냐에 따라 달라진다. 각 곡선에는 곡률 $c$와 기본 길이 $s$가 있다. 구체적으로 Sam이 차선 $i$에 있으면 이 곡선을 도는 동안 $s + c \cdot i$미터를 이동한다.

Sam은 직선 구간에 있을 때마다 인접한 차선으로 차선을 바꿀 수 있다. 인접한 차선으로 바꿀 때 Sam은 앞으로 $k$미터를 이동하지만 총 $k+r$미터를 이동한 것으로 계산된다. 모든 차선 변경은 자동차가 현재 직선 구간의 끝에 도달하기 전에 끝나야 한다. Sam은 같은 직선 구간에서 여러 번 차선을 바꿀 수 있다. 안전상의 이유로 곡선에서는 차선을 바꿀 수 없다.

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

첫 번째 줄에는 직선 구간의 수 $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이 이동해야 하는 최소 거리를 출력한다.