在 XY 平面上，给定两个点 $(p, q)$ 和 $(p', q')$，$L_\infty$ 距离定义为 $\max(|p - p'|, |q - q'|)$。在本题中，给定四个整数 $n, d, s, t$。假设你最初站在点 $(0, 0)$，需要移动到点 $(s, t)$。为此，你需要恰好进行 $n$ 次跳跃。在每次跳跃中，你必须在 $L_\infty$ 度量下移动恰好 $d$ 的距离。此外，跳跃到达的点必须是 XY 平面上的格点。也就是说，当你站在点 $(p, q)$ 时，如果 $p'$ 和 $q'$ 是整数且满足 $\max(|p - p'|, |q - q'|) = d$，则可以通过单次跳跃移动到新点 $(p', q')$。

注意，即使你在进行 $n$ 次跳跃之前到达了目标点 $(s, t)$，你也不能停止跳跃。

为了增加问题的趣味性，假设每次跳跃都会产生一定的代价。给定 $2n$ 个额外的整数 $x_1, y_1, x_2, y_2, \dots, x_n, y_n$，使得对于每个 $1 \le i \le n$，满足 $\max(|x_i|, |y_i|) = d$。第 $i$ 次（从 1 开始计数）跳跃的代价定义如下：设 $(p, q)$ 为你在第 $i$ 次跳跃前所站的点。考虑你可以跳到的所有格点集合。注意，该集合由某个正方形边上的所有格点组成。我们将整数 $1$ 分配给点 $(p + x_i, q + y_i)$。然后，我们将整数 $2, 3, \dots, 8d$ 按逆时针顺序分配给集合中的其余点。（此处假设 x 轴的正方向为右，y 轴的正方向为上。）这些整数代表你跳到这些点时所产生的代价。

例如，图 K.1 展示了当 $d = 2$ 且你位于 $(3, 1)$ 时，第 $i$ 次跳跃可到达的点。数字表示 $x_i = 1$ 和 $y_i = 2$ 时的代价。

图 K.1. 可到达的点及其代价

计算并输出目标所需的最小代价总和。

输入格式

输入包含单个测试用例。

第一行包含四个整数。$n$ ($1 \le n \le 40$) 是要进行的跳跃次数。$d$ ($1 \le d \le 10^{10}$) 是单次跳跃必须移动的 $L_\infty$ 距离。$s$ 和 $t$ ($|s|, |t| \le nd$) 是目标点的 x 和 y 坐标。保证至少有一种通过进行 $n$ 次跳跃到达目标点的方法。

接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，满足 $\max(|x_i|, |y_i|) = d$。

输出格式

输出到达目标点所需的最小代价。

样例

样例输入 1

3 2 4 0
2 2
-2 -2
-2 2

样例输出 1

15

样例输入 2

4 1 2 -2
1 -1
1 0
1 1
-1 0

样例输出 2

10

样例输入 3

6 5 0 2
5 2
-5 2
5 0
-3 5
-5 4
5 5

样例输出 3

24

样例输入 4

5 91 -218 -351
91 91
91 91
91 91
91 91
91 91

样例输出 4

1958

样例输入 5

1 10000000000 -10000000000 -2527532346
8198855077 10000000000

样例输出 5

30726387424