L∞ Jumps

For two points $(p, q)$ and $(p', q')$ in the XY-plane, the L∞ distance between them is defined as $\max(|p - p'|, |q - q'|)$.

You are given four integers $n, d, s, t$. You start at point $(0, 0)$ and need to move to point $(s, t)$. To do so, you perform exactly $n$ jumps. Each jump must move exactly $d$ in L∞ distance, and the point you reach by a jump must be a lattice point. That is, when you are standing at point $(p, q)$, you can move to point $(p', q')$ with a single jump if $p'$ and $q'$ are integers and $\max(|p - p'|, |q - q'|) = d$.

You cannot stop jumping even if you reach the destination $(s, t)$ before performing all $n$ jumps.

Each jump has a cost. You are given $2n$ more integers $x_1, y_1, x_2, y_2, \dots, x_n, y_n$ with $\max(|x_i|, |y_i|) = d$ for every $1 \le i \le n$. The cost of the $i$-th jump (1-indexed) is defined as follows. Let $(p, q)$ be the point where you stand just before the $i$-th jump. The lattice points you can jump to are exactly the lattice points on the boundary of a certain square. Assign the integer 1 to point $(p + x_i, q + y_i)$. Then assign $2, 3, \dots, 8d$ to the remaining points of the set in counterclockwise order. Here the positive x direction is to the right and the positive y direction is up. The assigned integer is the cost of jumping to that point.

For example, let $d = 2$, the current position be $(3, 1)$, $x_i = -1$ and $y_i = -2$. The reachable points are the 16 lattice points on the boundary of the square $1 \le x \le 5$, $-1 \le y \le 3$. Point $(2, -1)$ has cost 1, and going counterclockwise, $(3, -1)$ has cost 2, $(4, -1)$ has cost 3, $(5, -1)$ has cost 4, $(5, 0)$ has cost 5, $(5, 3)$ has cost 8, $(1, 3)$ has cost 12, and $(1, -1)$ has cost 16.

Find the minimum total cost to reach the destination.

The input consists of a single test case.

n d s t
x1 y1
x2 y2
...
xn yn

The first line contains four integers. $n$ ($1 \le n \le 40$) is the number of jumps. $d$ ($1 \le d \le 10^{10}$) is the L∞ distance that each jump must cover. $s$ and $t$ ($|s|, |t| \le nd$) are the x and y coordinates of the destination. At least one way to reach the destination with $n$ jumps is guaranteed to exist.

The $i$-th of the following $n$ lines contains two integers $x_i$ and $y_i$ with $\max(|x_i|, |y_i|) = d$.

Print the minimum cost required to reach the destination.