L∞ 점프

XY 평면 위의 두 점 $(p, q)$와 $(p', q')$ 사이의 L∞ 거리는 $\max(|p - p'|, |q - q'|)$로 정의한다.

네 정수 $n, d, s, t$가 주어진다. 처음에 점 $(0, 0)$에 서 있고, 점 $(s, t)$로 이동해야 한다. 이를 위해 점프를 정확히 $n$번 한다. 점프 한 번에 L∞ 거리로 정확히 $d$만큼 이동해야 하고, 점프로 도착하는 점은 격자점이어야 한다. 즉 점 $(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부터 센다)의 비용은 다음과 같이 정한다. $i$번째 점프 직전에 서 있는 점을 $(p, q)$라고 하자. 이 점프로 갈 수 있는 격자점의 집합은 어떤 정사각형의 둘레 위에 있는 격자점 전체이다. 점 $(p + x_i, q + y_i)$에 정수 1을 배정하고, 집합의 나머지 점에는 반시계 방향 순서로 $2, 3, \dots, 8d$를 배정한다. 이때 x축은 오른쪽이 양의 방향이고 y축은 위쪽이 양의 방향이다. 배정된 정수가 그 점으로 점프할 때의 비용이다.

예를 들어 $d = 2$이고 현재 위치가 $(3, 1)$이며 $x_i = -1$, $y_i = -2$이면, 갈 수 있는 점은 $1 \le x \le 5$, $-1 \le y \le 3$인 정사각형의 둘레 위에 있는 격자점 16개이다. 비용은 $(2, -1)$이 1이고, 반시계 방향으로 $(3, -1)$이 2, $(4, -1)$이 3, $(5, -1)$이 4, $(5, 0)$이 5, $(5, 3)$이 8, $(1, 3)$이 12, $(1, -1)$이 16이다.

목적지에 도착하는 데 드는 비용 합의 최솟값을 구하라.

입력은 테스트 케이스 하나로 이루어진다.

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

첫째 줄에 정수 네 개가 주어진다. $n$ ($1 \le n \le 40$)은 점프 횟수이다. $d$ ($1 \le d \le 10^{10}$)는 점프 한 번에 이동해야 하는 L∞ 거리이다. $s$와 $t$ ($|s|, |t| \le nd$)는 목적지의 $x$좌표와 $y$좌표이다. 점프 $n$번으로 목적지에 도착하는 방법이 적어도 하나 있음이 보장된다.

다음 $n$개의 줄 중 $i$번째 줄에는 두 정수 $x_i$와 $y_i$가 주어지며, $\max(|x_i|, |y_i|) = d$이다.

목적지에 도착하는 데 필요한 최소 비용을 출력한다.