4347: 「JOI 2017 Final」足球
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T4「[サッカー](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Soccer](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**
> 「假定球滚动时可以穿过其他球员」这句是在未修改数据的前提下，为了严谨我补上的，原题没有提这一点。如果撞到其他球员就停下的话似乎做法不同？
你是 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提示
输入样例2
3 3 0 50 10 2 0 0 3 3
输出样例2
60
输入样例3
4 3 0 15 10 2 0 0 4 3
输出样例3
45
输入样例4
4 6 0 5 1000 6 3 1 4 6 3 0 3 0 4 0 0 4
输出样例4
2020
数据范围：对于 $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)$。