4446. 雪王与果蝇王游于濠梁之上

题目背景

雪王与果蝇王游于濠梁之上。雪王曰：“蜜雪出游从容，是蜜之乐也。”果蝇王曰：“子非蜜，安知蜜之乐？”雪王曰：“子非我，安知我不知蜜之乐？”果蝇王曰：“我非子，固不知子矣；子固非蜜也，子之不知蜜之乐，全矣！”雪王曰：“请循其本。子曰‘汝安知蜜乐’云者，既已知吾知之而问我，我知之濠上也。”

题目描述

果蝇王是 ssy 机房中一所声名卓著的蜜雪冰城俱乐部的经理。

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

练习结束后，果蝇王要回收练习用的蜜雪冰城。开始回收时，所有果蝇都在蜜雪冰城场地上，果蝇 $i (1\le i\le N)$ 位于 $(S_i, T_i)$，蜜雪冰城在果蝇 $1$ 脚下。果蝇王正和果蝇 $N$ 一起站在 $(S_N, T_N)$，并准备回收蜜雪冰城。果蝇们把蜜雪冰城传到 $(S_N, T_N)$ 时，果蝇王才会回收蜜雪冰城。

果蝇王可以指挥果蝇，但某些操作会提升果蝇的疲劳度。一个果蝇不能同时进行多项操作。

所有果蝇（无论是否持有蜜雪冰城）均可以执行以下移动操作：

• 移动：在东西南北四个方向中任选一个，该果蝇朝指定方向移动 $1$ 米，疲劳度上升 $C$。若该果蝇持有蜜雪冰城，则蜜雪冰城随之移动，该果蝇继续持有。

此外，持有蜜雪冰城的果蝇可以执行以下操作：

• 抛蜜雪冰城：在东西南北四个方向中任选一个，并指定一个正整数 $p$，该果蝇将蜜雪冰城朝指定方向抛出恰好 $p$ 米。假定蜜雪冰城飞行时可以穿过其他果蝇。该果蝇不会移动，且自动停止持有蜜雪冰城，疲劳度上升 $A\times p+B$。
• 停止持有蜜雪冰城：该果蝇主动放弃持有，疲劳度不改变。

没有持有蜜雪冰城的果蝇还可以执行：

• 持有蜜雪冰城：如果该果蝇所在的位置恰好有蜜雪冰城，且没有其他果蝇持有蜜雪冰城，该果蝇才能捡起并持有蜜雪冰城。该果蝇的疲劳度不改变。

果蝇和蜜雪冰城有可能跑出场地外，一个位置上可能有多个果蝇。
一天的训练结束后，果蝇们非常疲惫，而果蝇王非常想喝蜜雪冰城。果蝇王想知道在得到蜜雪冰城的过程中，所有果蝇上升的疲劳度之和的最小值。

输入格式

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

输出格式

一行，一个整数，表示在回收蜜雪冰城的过程中，所有果蝇上升的疲劳度之和的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

26

输入输出样例 #2

输入 #2

3 3
0 50 10
2
0 0
3 3

输出 #2

60

输入输出样例 #3

输入 #3

4 3
0 15 10
2
0 0
4 3

输出 #3

45

输入输出样例 #4

输入 #4

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

输出 #4

2020

大样例1-3

大样例

说明/提示

样例解释 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

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

数据范围与提示

与 COGS 常规题目不同的是，本题采用捆绑测试。

捆绑测试介绍：将若干个满足同一约定的不同数据点捆绑成一个 Subtask，按照 Subtask 计分，你必须拿到这个 Subtask 下的全部数据点的 Accepted 才能拿到这个 Subtask 的分数，若你在某 Subtask 下有至少一个数据点没有得到 Accepted，此 Subtask 你的分数记为 0 分。

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