#2335. 「JOI 2017 Final」足球

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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 ,用空格分隔。
输入的所有数的含义见题目描述。

输出格式

一行,一个整数,表示在回收球的过程中,所有球员上升的疲劳度之和的最小值。

样例

样例输入 1

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

样例输出 1

26

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

3 3
0 50 10
2
0 0
3 3

样例输出 2

60

样例解释 2

在最优解中,不需要踢球。

样例输入 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

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