AT_joi2017ho_d サッカー (Soccer)

平面直角坐标系上，有一个足球场，横坐标范围 $[0,X]$，纵坐标范围 $[0,Y]$。 开始时，球场上站了 $N$ 个球员，坐标分别为 $(x_i,y_i)$。 球在开始时 $1$ 号球员的位置上，你希望让这 个球到开始时 $N$ 号球员的位置上。 你可以指挥任一球员进行下列某一操作，但某些操作会提升球员的疲劳度。指挥次数不限但应当有 明确的先后顺序。 已知每个球员有两种状态：控球和没有控球。 你可以指挥控球的球员进行如下操作： • 踢球。在上下左右四个方向中任选一个，并指定一个正整数 $p$ ，该球员将球朝指定方向踢出恰好 $p$ 个单位。该球员不会移动，且自动停止控球，疲劳度上升$A×p+B$。 • 运球。在上下左右四个方向中任选一个，该球员带球，朝指定方向移动 $1$ 个单位。疲劳度上升 $C$。 • 停止控球。该球员的疲劳度不改变。 你可以指挥没有控球的球员进行如下操作： • 移动。在上下左右四个方向中任选一个，该球员朝指定方向移动 $1$ 个单位，疲劳度上升 $C$。 • 控球。如果该球员所在的位置恰好有球，且没有其他球员控球，该球员才能控球。该球员的疲劳 度不改变。 **球员和球有可能跑出场外，一个位置上可能有多个球员。 球员可视作质点，因此球滚动和运球时都不会因为碰到球员而停下。** 让球滚到指定位置的过程中，求所有球员上升的疲劳度之和的最小值。

第一行两个整数 $X$ , $Y$ 用空格分隔。 第二行三个整数 $A$ $B$ $C$，用空格分隔。 第三行一个整数 $N$。接下来的 $N$ 行，第 $i$ 行两个整数 $x_i$，$y_i$，用空格分隔。

一行，一个整数，表示所有球员上升的疲劳度之和的最小值。

### 課題 グラウンドの大きさおよび選手たちの位置が与えられたとき，片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 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 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 入力例 $ 1 $ は，小課題 $ 1 $ および小課題 $ 2 $ の条件を満たしていない．この入力例では，グラウンドは下図の状態となっている．図において，白い丸は選手を，黒い丸はボールを表している．あなたは $ (6,\ 5) $ にいる． !\[\](https://img.atcoder.jp/joi2017ho/ebb97800b8fa098db87231894ceada5e.png)グラウンドの初期状態 この場合，以下のように行動すればよい． 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 $ となり，これが最小値となる． !\[\](https://img.atcoder.jp/joi2017ho/c7d772b426c740eaffe243afd3a09f94.png)最適解における行動の様子 - - - - - - ### Sample Explanation 2 入力例 $ 2 $ は，小課題 $ 1 $ および小課題 $ 2 $ の条件を満たしている．入力例 $ 2 $ において，ボールを蹴る必要はない． - - - - - - ### Sample Explanation 3 入力例 $ 3 $ は，小課題 $ 1 $ および小課題 $ 2 $ の条件を満たしている． - - - - - - ### Sample Explanation 4 入力例 $ 4 $ は，小課題 $ 1 $ の条件を満たしておらず，小課題 $ 2 $ の条件を満たしている．同じ地点に複数の選手がいる場合が含まれることに注意せよ．