题目描述

题目译自 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)$。