#P5100. [JOI 2017 Final] 足球

[JOI 2017 Final] 足球

题目描述

题目译自 JOI 2017 Final T4「サッカー / Soccer

「假定球滚动时可以穿过其他球员」这句是在未修改数据的前提下,为了严谨我补上的,原题没有提这一点。如果撞到其他球员就停下的话似乎做法不同?

你是 JOI 联赛中一所声名卓著的足球俱乐部的经理。

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

练习结束后,你要回收练习用的足球。开始回收时,所有球员都在足球场上,球员 i(1iN)i (1\leqslant i\leqslant N) 位于 (Si,Ti)(S_i, T_i),球在球员 11 脚下。你正和球员 NN 一起站在 (SN,TN)(S_N, T_N),并准备回收球。球员们把球传到 (SN,TN)(S_N, T_N) 时,你才会回收球。

你可以指挥球员,但某些操作会提升球员的疲劳度。一个球员不能同时进行多项操作。
你可以指挥控球的球员进行如下操作:

  • 踢球。在东西南北四个方向中任选一个,并指定一个正整数 pp,该球员将球朝指定方向踢出恰好 pp 米。假定球滚动时可以穿过其他球员。该球员不会移动,且自动停止控球,疲劳度上升 A×p+BA\times p+B
  • 运球。在东西南北四个方向中任选一个,该球员带球,朝指定方向移动 11 米。该球员仍然控球,疲劳度上升 CC
  • 停止控球。该球员的疲劳度不改变。

你可以指挥没有控球的球员进行如下操作:

  • 移动。在东西南北四个方向中任选一个,该球员朝指定方向移动 11 米,疲劳度上升 CC
  • 控球。如果该球员所在的位置恰好有球,且没有其他球员控球,该球员才能控球。该球员的疲劳度不改变。

球员和球有可能跑出场外,一个位置上可能有多个球员。
一天的训练结束后,球员们非常疲惫。你想知道在回收球的过程中,所有球员上升的疲劳度之和的最小值。

输入格式

第一行有两个整数 H,WH, W,用空格分隔。
第二行有三个整数 A,B,CA, B, C,用空格分隔。
第三行有一个整数 NN
在接下来的 NN 行中,第 ii(1iN)(1\leqslant i\leqslant N)有两个整数 Si,TiS_i, T_i,用空格分隔。
输入的所有数的含义见题目描述。

输出格式

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

6 5
1 3 6
3
1 1
0 4
6 5
26
3 3
0 50 10
2
0 0
3 3
60
4 3
0 15 10
2
0 0
4 3
45
4 6
0 5 1000
6
3 1
4 6
3 0
3 0
4 0
0 4
2020

提示

样例解释 1

在这组样例中,球场、球员、球处于如图所示的状态。图中,黑框空心圆圈表示球员,实心圆表示球,你在 (6,5)(6,5)

初始状态

最优解如下:

  1. 球员 11 把球向东踢出 33 米。疲劳度上升了 1×3+3=61\times 3+3=6,球移动到 (1,4)(1,4)
  2. 球员 22 向南移动 11 米。疲劳度又上升了 66
  3. 球员 22 开始控球。
  4. 球员 22 向东运球 11 米。疲劳度又上升了 66
  5. 球员 22 把球向南踢出 55 米,疲劳度上升了 1×5+3=81\times 5+3=8,球移动到 (6,5)(6,5)

此时,疲劳度之和为 6+6+6+8=266+6+6+8=26。没有更好的方案。

最优解

样例解释 2

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

样例解释 4

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

数据范围与提示

对于 5%5\% 的数据,N=2N=2
对于另外 30%30\% 的数据,N1000,A=0N\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)$。