#P3. [Sleeping Cup #1] Moving like a spider

[Sleeping Cup #1] Moving like a spider

注意

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

题目描述

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

如图,这是一张蜘蛛网。这张蜘蛛网有以下要素:

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

现有 mm 只蜘蛛在这个蜘蛛网上运动,它们的初始位置已知(保证都不是中心点 OO,因此都可以用坐标表示)。

每只蜘蛛都可以进行若干次运动(次数由你决定,也可以是 00 次)。一般来说,每次运动都有 44 个方向可选。当起点为 (x0,y0)(x_0,y_0) 时:

方向 图中体现 终点 花费体力 特例
沿射线运动,远离中心点 OO (x0,y0+1)(x_0,y_0+1) 00 (1)
沿射线运动,靠近中心点 OO (x0,y01)(x_0,y_0-1) dd (2)
沿圆顺时针运动 (x01,y0)(x_0-1,y_0) ry0ry_0 (3)
沿圆逆时针运动 (x0+1,y0)(x_0+1,y_0) (4)

其中,最后一列 44 个格子的内容从上到下分别是:

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

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

输入格式

第一行,四个正整数,m,n,d,rm,n,d,r

接下来 mm 行,第 ii 行两个整数 xi,yix_i,y_i,表示第 ii 只蜘蛛的初始位置 (xi,yi)(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

提示

样例 11 解释:

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

  • 11 号蜘蛛沿 (0,2)(0,3)(0,4)(0,5)(0,2) \to (0,3) \to (0,4) \to (0,5) 的路径运动(即向上运动 33 次),花费的体力为 0+0+0=00+0+0=0
  • 22 号蜘蛛沿 (6,4)(0,4)(0,5)(6,4) \to (0,4) \to (0,5) 的路径运动(即先向右运动 11 次,再向上运动 11 次),花费的体力为 8×4+0=328 \times 4 + 0 = 32
  • 33 号蜘蛛待在原地即可,花费的体力为 00

故答案为 0+32+0=320+32+0=32

样例 22 解释:

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

  • 11 号蜘蛛沿 (0,1)O(1,1)(0,1) \to O \to (1,1) 的路径运动(即先向下运动 11 次,再向上运动 11 次),花费的体力为 3+0=33+0=3
  • 22 号蜘蛛待在原地即可,花费的体力为 00

故答案为 3+0=33+0=3


对于 100%100\% 的数据,2m,n1052 \le m,n \le 10^51yi1051 \le y_i \le 10^51d,r1081 \le d,r \le 10^80xin10 \le x_i \le n-1