该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意

本题需要使用文件读写（spider.in / spider.out）。

题目描述

这里有一张图片。如果你没有看到，请点击右侧的「文件」以下载或查看。

如图，这是一张蜘蛛网。这张蜘蛛网有以下要素：

• 中心点 $O$，即图中左侧用黄字标出的那个点；
• 由中心点 $O$ 引出的 $n$ 条射线（图中只画了 $4$ 条），分别记为直线 $x=0$，$x=1$，$x=2$，……，$x=n-1$；
• 足够多个以中心点 $O$ 为圆心的同心圆（图中只画了 $3$ 个，并且每个圆只画了一段圆弧），分别记为圆 $y=1$，$y=2$，$y=3$，……。
• 圆与射线形成的若干个交点（除了中心点 $O$），其中圆 $y=y_0$ 和射线 $x=x_0$ 的交点将被记为 $(x_0,y_0)$。例如，图中右上角的那个交点将被记为 $(2,3)$。

现有 $m$ 只蜘蛛在这个蜘蛛网上运动，它们的初始位置已知（保证都不是中心点 $O$，因此都可以用坐标表示）。

每只蜘蛛都可以进行若干次运动（次数由你决定，也可以是 $0$ 次）。一般来说，每次运动都有 $4$ 个方向可选。当起点为 $(x_0,y_0)$ 时：

其中，最后一列 $4$ 个格子的内容从上到下分别是：

1. 当起点是中心点 $O$ 时（实际上，当起点是中心点 $O$ 时，只能向上运动），终点可以是 $(0,1),(1,1),\ldots,(n-1,1)$ 中的任何一个，具体是哪一个由你决定。
2. 当 $y_0=1$ 时，终点将是中心点 $O$。
3. 当 $x_0=0$ 时，终点将是 $(n-1,y_0)$。
4. 当 $x_0=n-1$ 时，终点将是 $(0,y_0)$。

现在，这 $m$ 只蜘蛛需要会合。请你帮它们选择一个合适的会合地点（要么是中心点 $O$，要么是某个圆与射线形成的交点），并合理规划每只蜘蛛的运动路线，使得这 $m$ 只蜘蛛运动所花费的体力之和最小，并给出这个最小体力和。

输入格式

第一行，四个正整数，$m,n,d,r$。

接下来 $m$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示第 $i$ 只蜘蛛的初始位置 $(x_i,y_i)$。

输出格式

一行一个整数，表示答案。

样例

3 7 9 8
0 2
6 4
0 5

32

2 2 3 5
0 1
1 1

3

7 11 63599913 20656382
9 9
1 11
6 4
0 4
1 15
2 11
6 20

2393965956

提示

样例 $1$ 解释：

一种最优的方案是，将会合点选在 $(0,5)$：

• $1$ 号蜘蛛沿 $(0,2) \to (0,3) \to (0,4) \to (0,5)$ 的路径运动（即向上运动 $3$ 次），花费的体力为 $0+0+0=0$；
• $2$ 号蜘蛛沿 $(6,4) \to (0,4) \to (0,5)$ 的路径运动（即先向右运动 $1$ 次，再向上运动 $1$ 次），花费的体力为 $8 \times 4 + 0 = 32$；
• $3$ 号蜘蛛待在原地即可，花费的体力为 $0$。

故答案为 $0+32+0=32$。

样例 $2$ 解释：

一种最优的方案是，将会合点选在 $(1,1)$：

• $1$ 号蜘蛛沿 $(0,1) \to O \to (1,1)$ 的路径运动（即先向下运动 $1$ 次，再向上运动 $1$ 次），花费的体力为 $3+0=3$；
• $2$ 号蜘蛛待在原地即可，花费的体力为 $0$。

故答案为 $3+0=3$。

对于 $100\%$ 的数据，$2 \le m,n \le 10^5$，$1 \le y_i \le 10^5$，$1 \le d,r \le 10^8$，$0 \le x_i \le n-1$。