Person in Charge

• 035966_L3

Attention

This problem requires file I/O (spider.in / spider.out).

Problem Description

An image is available here. If not visible, download it from the "Attachments" section.

As shown in the image, this is a spider web with the following elements:

• Central point $O$, marked in yellow on the left side of the figure;
• $n$ rays emanating from $O$ (only $4$ are drawn in the figure), labeled as lines $x=0$, $x=1$, $x=2$, ..., $x=n-1$;
• Multiple concentric circles centered at $O$ (only $3$ are drawn in the figure, with partial arcs shown), labeled as circles $y=1$, $y=2$, $y=3$, ...;
• Intersection points formed by the circles and rays (excluding $O$). The intersection of circle $y=y_0$ and ray $x=x_0$ is denoted as $(x_0,y_0)$. For example, the top-right intersection in the figure is $(2,3)$.

There are $m$ spiders moving on this web, with their initial positions given (guaranteed not to be $O$, so they can all be represented by coordinates).

Each spider can move multiple times (the number of moves is up to you, including 0 moves). Generally, there are $4$ possible directions for each move. When starting from $(x_0,y_0)$:

Direction	Visualization	Destination	Energy Cost	Special Cases
Up	Move along the ray away from $O$	$(x_0,y_0+1)$	$0$	(1)
Down	Move along the ray toward $O$	$(x_0,y_0-1)$	$d$	(2)
Left	Move clockwise along the circle	$(x_0-1,y_0)$	$ry_0$	(3)
Right	Move counterclockwise along the circle	$(x_0+1,y_0)$		(4)

The special cases (last column) are:

1. If the starting point is $O$ (in which case the only possible move is "up"), the destination can be any of $(0,1),(1,1),...,(n-1,1)$, chosen by you.
2. If $y_0=1$, the destination will be $O$.
3. If $x_0=0$, the destination will be $(n-1,y_0)$.
4. If $x_0=n-1$, the destination will be $(0,y_0)$.

Now, these $m$ spiders need to gather at a meeting point (either $O$ or an intersection point). Your task is to choose an optimal meeting point and plan the movement paths for each spider to minimize the total energy cost, then output this minimum total energy.

Input Format

First line: Four positive integers, $m,n,d,r$.

Next $m$ lines: The $i$-th line contains two integers $x_i,y_i$, representing the initial position $(x_i,y_i)$ of the $i$-th spider.

Output Format

One integer: The answer.

Samples

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

Explanation for Sample 1

An optimal solution is to choose $(0,5)$ as the meeting point:

• Spider $1$ moves along $(0,2) \to (0,3) \to (0,4) \to (0,5)$ (3 "up" moves), costing $0+0+0=0$;
• Spider $2$ moves along $(6,4) \to (0,4) \to (0,5)$ (1 "right" move and 1 "up" move), costing $8 \times 4 + 0 = 32$;
• Spider $3$ stays in place, costing $0$.

The total cost is $0+32+0=32$.

Explanation for Sample 2

An optimal solution is to choose $(1,1)$ as the meeting point:

• Spider $1$ moves along $(0,1) \to O \to (1,1)$ (1 "down" move and 1 "up" move), costing $3+0=3$;
• Spider $2$ stays in place, costing $0$.

The total cost is $3+0=3$.

Data Range

For $100\%$ of the data: $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$.

Attachments

Download the files here.

Official Solution

link