You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

题目译自 JOI 2017 Final T4「サッカー / Soccer」

「假定球滚动时可以穿过其他球员」这句是在未修改数据的前提下，为了严谨我补上的，原题没有提这一点。如果撞到其他球员就停下的话似乎做法不同？

你是 JOI 联赛中一所声名卓著的足球俱乐部的经理。

俱乐部有 $N$ 名球员，编号为 $1\ldots N$。球员们每天都刻苦地进行训练，剑指联赛冠军。足球场可视为一个底为 $W$ 米，高 $H$ 米的长方形，底平行于东西方向，高平行于南北方向。如果某个点向北走 $i$ 米，再向西走 $j$ 米恰好到达球场的西北角，这个点可用坐标 $(i, j)$ 来表示。

练习结束后，你要回收练习用的足球。开始回收时，所有球员都在足球场上，球员 $i (1\leqslant i\leqslant N)$ 位于 $(S_i, T_i)$，球在球员 $1$ 脚下。你正和球员 $N$ 一起站在 $(S_N, T_N)$，并准备回收球。球员们把球传到 $(S_N, T_N)$ 时，你才会回收球。

你可以指挥球员，但某些操作会提升球员的疲劳度。一个球员不能同时进行多项操作。
你可以指挥控球的球员进行如下操作：

• 踢球。在东西南北四个方向中任选一个，并指定一个正整数 $p$，该球员将球朝指定方向踢出恰好 $p$ 米。假定球滚动时可以穿过其他球员。该球员不会移动，且自动停止控球，疲劳度上升 $A\times p+B$。
• 运球。在东西南北四个方向中任选一个，该球员带球，朝指定方向移动 $1$ 米。该球员仍然控球，疲劳度上升 $C$。
• 停止控球。该球员的疲劳度不改变。

你可以指挥没有控球的球员进行如下操作：

• 移动。在东西南北四个方向中任选一个，该球员朝指定方向移动 $1$ 米，疲劳度上升 $C$。
• 控球。如果该球员所在的位置恰好有球，且没有其他球员控球，该球员才能控球。该球员的疲劳度不改变。

球员和球有可能跑出场外，一个位置上可能有多个球员。
一天的训练结束后，球员们非常疲惫。你想知道在回收球的过程中，所有球员上升的疲劳度之和的最小值。

输入格式

第一行有两个整数 $H, W$，用空格分隔。
第二行有三个整数 $A, B, C$，用空格分隔。
第三行有一个整数 $N$。
在接下来的 $N$ 行中，第 $i$ 行 $(1\leqslant i\leqslant N)$有两个整数 $S_i, T_i$，用空格分隔。
输入的所有数的含义见题目描述。

输出格式

一行，一个整数，表示在回收球的过程中，所有球员上升的疲劳度之和的最小值。

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

26

3 3
0 50 10
2
0 0
3 3

60

4 3
0 15 10
2
0 0
4 3

45

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

2020

提示

样例解释 1

在这组样例中，球场、球员、球处于如图所示的状态。图中，黑框空心圆圈表示球员，实心圆表示球，你在 $(6,5)$。

最优解如下：

1. 球员 $1$ 把球向东踢出 $3$ 米。疲劳度上升了 $1\times 3+3=6$，球移动到 $(1,4)$。
2. 球员 $2$ 向南移动 $1$ 米。疲劳度又上升了 $6$。
3. 球员 $2$ 开始控球。
4. 球员 $2$ 向东运球 $1$ 米。疲劳度又上升了 $6$。
5. 球员 $2$ 把球向南踢出 $5$ 米，疲劳度上升了 $1\times 5+3=8$，球移动到 $(6,5)$。

此时，疲劳度之和为 $6+6+6+8=26$。没有更好的方案。

样例解释 2

在最优解中，不需要踢球。

样例解释 4

注意这组样例中有多个球员在同一位置的情况。

数据范围与提示

对于 $5\%$ 的数据，$N=2$。
对于另外 $30\%$ 的数据，$N\leqslant 1000, A=0$。
对于所有数据，$1\leqslant H,W\leqslant 500, 0\leqslant A, B, C\leqslant 10^9, 2\leqslant N\leqslant 10^5, 0\leqslant S_i\leqslant H, 0\leqslant T_i\leqslant W(1\leqslant i\leqslant N), (S_1, T_1)\neq(S_N, T_N)$。