你是 JOI 联赛中一支著名足球队的经理。

球队共有 $N$ 名球员，编号为 $1$ 到 $N$。球员们正在刻苦训练以赢得锦标赛。球场是一个高为 $H$ 米、宽为 $W$ 米的矩形。球场的纵向为南北方向，横向为东西方向。球场上的点用 $(i, j)$ 表示，即从球场西北角向南 $i$ 米、向东 $j$ 米处。

训练结束后，球员们必须清理球场上的球。清理开始时，球员 $i$ ($1 \le i \le N$) 站在 $(S_i, T_i)$ 处。场上只有一个球，且球员 $1$ 持有该球。你和球员 $N$ 站在 $(S_N, T_N)$ 处。当球被传到 $(S_N, T_N)$ 且你接住它时，清理工作完成。在清理过程中，你不能移动。

你可以要求球员采取行动。但是，如果一名球员采取行动，他的疲劳度会根据行动而增加。以下是球员可能采取的行动列表。如果球员持有球，他可以采取 (i)、(ii) 或 (iii) 行动。否则，他可以采取 (ii) 或 (iv) 行动。

(i) 选择 4 个方向（东/西/南/北）中的一个，并选择一个正整数 $p$。将球向该方向踢出。球会移动恰好 $p$ 米。踢球者在此行动中不会移动，且会失去球。他的疲劳度增加 $A \times p + B$。

(ii) 选择 4 个方向（东/西/南/北）中的一个，并向该方向移动 1 米。如果他持有球，他会带着球一起移动。无论是否持有球，他的疲劳度都会增加 $C$。

(iii) 将球放置在他站立的位置。他失去球。他的疲劳度不变。

(iv) 捡起球。他的疲劳度不变。球员仅在与球处于同一位置且无人持球时才能采取此行动。

注意，球员或球有可能离开球场。多名球员可以站在同一个位置。

由于球员们刚结束训练，他们的疲劳度增加不能过多。你希望计算出清理过程中球员疲劳度之和的最小值。

任务

给定球场的大小和球员的位置，编写一个程序，计算清理过程中球员疲劳度之和的最小值。

输入格式

从标准输入读取以下数据：

• 第一行包含两个空格分隔的整数 $H, W$。这意味着球场是一个高为 $H$ 米、宽为 $W$ 米的矩形。
• 第二行包含三个空格分隔的整数 $A, B, C$，描述行动导致的疲劳度增加。
• 第三行包含一个整数 $N$，即球员人数。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含两个空格分隔的整数 $S_i, T_i$。这意味着在清理开始时，球员 $i$ ($1 \le i \le N$) 站在 $(S_i, T_i)$ 处。

输出格式

将结果写入标准输出。输出包含清理过程中球员疲劳度之和的最小值。

数据范围

所有输入数据满足以下条件：

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

子任务

子任务 1 [5 分]

• $N = 2$

子任务 2 [30 分]

满足以下条件： $N \le 1\,000$ $A = 0$

子任务 3 [65 分]

无附加限制。

样例

样例输入 1

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

样例输出 1

26

初始状态

球员采取以下行动： 1. 球员 1 将球向东踢出 3 米。他的疲劳度增加 $1 \times 3 + 3 = 6$。球移动到 $(1, 4)$。 2. 球员 2 向南移动 1 米，他持有球。他的疲劳度增加 6。 3. 球员 2 向东移动 1 米。他的疲劳度增加 6。 4. 球员 2 将球向南踢出 5 米。他的疲劳度增加 $1 \times 5 + 3 = 8$。球移动到 $(6, 5)$。

在这些行动中，疲劳度之和为 $6 + 6 + 6 + 8 = 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