Problem Description

Input Format

Read the following input from standard input:

• The first line contains two integers $ H, W $ separated by a space. These represent the ground being a rectangle $ H $ meters high and $ W $ meters wide.
• The second line contains three integers $ A, B, C $ separated by a space, related to the increase in fatigue.
• The third line contains an integer $ N $, indicating the number of players.
• The following $ N $ lines, where the $ i $-th line ($1 \leq i \leq N$) contains two integers $ S_i, T_i $ separated by a space. These indicate that player $ i $ is at position $ (S_i, T_i) $ at the start of cleanup.

Output Format

Output to standard output the minimum total fatigue value that can occur due to cleanup on a single line.

Sample Input and Output

Sample Input #1

6 5
1 3 6
3
1 1
0 4
6 5

Sample Output #1

26

Sample Input #2

3 3
0 50 10
2
0 0
3 3

Sample Output #2

60

Sample Input #3

4 3
0 15 10
2
0 0
4 3

Sample Output #3

45

Sample Input #4

4 6
0 5 1000
6
3 1
4 6
3 0
3 0
4 0
0 4

Sample Output #4

2020

Notes/Hints

Task

Given the size of the ground and the positions of the players, create a program to find the minimum total fatigue value that can occur due to cleanup.

Constraints

All input data satisfies the following conditions:

• $1 \leq H \leq 500$.
• $1 \leq W \leq 500$.
• $0 \leq A \leq 1,000,000,000$.
• $0 \leq B \leq 1,000,000,000$.
• $0 \leq C \leq 1,000,000,000$.
• $2 \leq N \leq 100,000$.
• $0 \leq S_i \leq H$ ($1 \leq i \leq N$).
• $0 \leq T_i \leq W$ ($1 \leq i \leq N$).
• $(S_1, T_1) \neq (S_N, T_N)$.

Subtasks

Subtask 1 [5 points]

• $ N = 2 $.

Subtask 2 [30 points]

Satisfies the following conditions:

• $N \leq 1,000$.
• $ A = 0 $.

Subtask 3 [65 points]

No additional constraints.

Sample Explanation 1

Sample input #1 does not satisfy the conditions of Subtask 1 and Subtask 2. In this input, the ground is in the following state. In the figure, white circles represent players, and black circles represent balls. You are at $ (6, 5) $. Initial state of the ground In this case, the following actions should be taken:

1. Player 1 kicks the ball 3 meters east. Fatigue increases by $1 \times 3 + 3 = 6$, and the ball moves to $ (1, 4) $.
2. Player 2 moves 1 meter south and takes possession of the ball. Fatigue increases by $ 6 $.
3. Player 2 moves 1 meter east. Fatigue increases by $ 6 $.
4. Player 2 kicks the ball 5 meters south. Fatigue increases by $1 \times 5 + 3 = 8$, and the ball moves to $ (6, 5) $.

In this case, the total fatigue value is $ 6 + 6 + 6 + 8 = 26 $, which is the minimum value. State of actions in the optimal solution

Sample Explanation 2

Sample input #2 satisfies the conditions of Subtask 1 and Subtask 2. In sample input #2, there is no need to kick the ball.

Sample Explanation 3

Sample input #3 satisfies the conditions of Subtask 1 and Subtask 2.

Sample Explanation 4

Sample input #4 does not satisfy the conditions of Subtask 1 and satisfies the conditions of Subtask 2. Note that multiple players can be at the same location.

见题面 Input 部分

见题面 Output 部分