在高速公路上过弯时，Sam 意识到如果走内侧车道，行驶的距离会更短。Sam 想知道到达目的地所需行驶的最短距离是多少。

这条多车道高速公路由一系列由弯道连接的直道组成。在通过弯道时，行驶的距离取决于你所处的车道。每个弯道都有一个弯曲度 $c$ 和延伸量 $s$。具体来说，如果 Sam 处于第 $i$ 条车道，那么他在通过该弯道时需要行驶 $s + c \cdot i$ 米。

每当 Sam 处于直道上时，他可以从当前车道变道至相邻车道。当变道至相邻车道时，Sam 会在直道方向上向前移动 $k$ 米，但实际行驶的总距离为 $k + r$ 米。每次变道都必须在车辆到达当前直道尽头之前完成。Sam 可以在同一条直道上多次变道。出于安全考虑，在弯道上无法进行变道。

Sam 从第 1 条车道出发，并希望在第 1 条车道结束。他必须行驶的最短距离是多少？

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 250$)，表示直道的数量，以及 $m$ ($1 \le m \le 250$)，表示高速公路上的车道数量。车道从 $1, 2, \dots, m$ 编号。

第二行包含两个整数 $k$ ($1 \le k \le 10^6$) 和 $r$ ($1 \le r \le 10^6$)，表示变道的参数。

接下来的 $n$ 行按顺序描述每条直道。这些行中的每一行都包含一个整数 $\ell$ ($1 \le \ell \le 10^6$)，表示该条直道的长度。

接下来的 $n - 1$ 行按顺序描述每个弯道。这些行中的每一行都包含两个整数 $s$ ($1 \le s \le 10^6$)，表示该弯道的延伸量，以及 $c$ ($-10^6 \le c \le 10^6$)，表示该弯道的弯曲度。保证 $s + c \cdot m > 0$。

第 $i$ 个弯道连接第 $i$ 条和第 $i+1$ 条直道。

输出格式

输出 Sam 必须行驶的最短距离。

样例

输入样例 1

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

输出样例 1

51

输入样例 2

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

输出样例 2

61