配点: 100 点
你是 JOI 联赛著名足球俱乐部的经理。
俱乐部有 N 名选手组成,选手有 1 减去 N 被标注了编号。选手们为了优胜每天在场地上练习。场地纵向 H 米,横向 W 它的形状为一米长方形。地面的垂直方向平行于南北方向,水平方向平行于东西方向。从地面西北角向南 i 向东米 j 指向您已行驶米数的点 我们称之为 (i, j) 。
练习结束后,练习用的球必须收起来。清理工作开始时,队员们 i (1 \leqq i \leqq N) 是一个点 (S_i, T_i) 并且球在玩家的位置 仅 1 仅有的 1 我有一个。你是一名玩家 N 带点 (S_N, T_N) ,你的任务是取回球,即将球放在 将其移至 (S_N, T_N) 即可完成清理。清洁过程中您不能移动。
你可以指挥玩家的行动。当玩家采取行动时,他们会根据该行动累积疲劳程度。
在以下动作中,控球球员可以执行动作(i)、(ii)和(iii),其他球员可以执行动作(ii)和(iv)。
(i) 北、南、东、西 4 方向不对 1 方向和正整数
指定 p 。朝那个方向踢球并准确击球 p 以米为单位移动。踢球的球员不会因该动作而移动,并且不再拥有球权。疲劳程度为
增加 A \times p + B 。
(ii) 北、南、东、西 4 方向不对 1 指定方向。朝那个方向 1 移动米。如果移动的球员有球,他就随球移动。有球或无球时的疲劳程度 C 。
(iii) 将球放在原地并处于您不再拥有球的状态。疲劳程度不会增加。
(iv) 控球。疲劳程度不会增加。此操作只能由与球处于同一位置的球员执行,并且只能在没有其他人控球的情况下执行。
请注意,如果球员或球离开场地,或者同一地点存在多个球员,这并不重要。
为了防止队员在练习后积累过多的疲劳,您决定找出队员因清理而产生的疲劳总量的最小可能值。
課題
给定场地的大小和球员的位置,编写一个程序,找出球员因清理而造成的最小可能总疲劳量。
入力
从标准输入读取以下输入。
- 1 在线 2 整数 给出了 H, W 以空格作为分隔符。这些地面是垂直的 H 米,横向 W 这表示它的形状为 1 米长方形。
- 2 线描述了疲劳程度的增加。 3 整数 给出了 A, B, C 以空格为分隔书写。
- 3 行是一个整数 N 。这是播放器 N 这表明有人。
- 继续 N 行 i 行目 (1 \leqq i \leqq N) 是 写入 2 整数 S_i, T_i 以空格作为分隔符。这些是清理开始时的玩家。 i 是重点 它代表处于 (S_i, T_i) 中。
出力
因清理而造成的玩家总疲劳程度的最小可能值被添加到标准输出中。 1 请按行输出。
制限
所有的输入数据满足以下条件。
- 1 \leqq H \leqq 500.
- 1 \leqq W \leqq 500.
- 0 \leqq A \leqq 1\,000\,000\,000.
- 0 \leqq B \leqq 1\,000\,000\,000.
- 0 \leqq C \leqq 1\,000\,000\,000.
- 2 \leqq N \leqq 100\,000.
- 0 \leqq S i \leqq H (1 \leqq i \leqq N).
- 0 \leqq Ti \leqq W (1 \leqq i \leqq N).
- (S_1, T_1) \neq (S_N, T_N).
小課題
小課題 1 [5 点]
- N = 2 很满意。
小課題 2 [30 点]
满足以下条件。
- N \leqq 1\,000.
- A = 0.
小課題 3 [65 点]
没有其他限制。
入力例 1
6 5 1 3 6 3 1 1 0 4 6 5
出力例 1
26
入力例 1 是一个小任务 1 和小作业 不满足 2 条件。在此输入示例中,接地处于如下所示的状态。图中,白色圆圈代表球员,黑色圆圈代表球。你是 我在 (6, 5) 。

在这种情况下,您可以按照以下方式操作。
- 選手 1 将球向东移动。 3 踢米。疲劳程度为 球上升 1 \times 3 + 3 = 6 移至 (1, 4) 。
- 選手 2 向南 1 移动米并控球。疲劳程度为 它增加了 6 。
- 選手 2 向东 1 移动仪表。疲劳程度为 6 。
- 選手 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
入力例 2 是一个小任务 1 和小作业 不满足 2 。输入示例 2 中无需踢球。
入力例 3
4 3 0 15 10 2 0 0 4 3
出力例 3
45
入力例 3 是一个小任务 1 和小作业 不满足 2 满足条件。
入力例 4
4 6 0 5 1000 6 3 1 4 6 3 0 3 0 4 0 0 4
出力例 4
2020
入力例 4 是一个小任务 1 条件,次要赋值为 2 满足条件。请注意,这包括同一位置有多个玩家的情况。