AT_joi2017ho_d サッカー (Soccer)

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_d

標準入力から以下の入力を読み込め． - $ 1 $ 行目には $ 2 $ 個の整数 $ H,\ W $ が空白を区切りとして書かれている．これらはグラウンドが縦に $ H $ メートル，横に $ W $ メートルの長方形の形状をしていることを表している． - $ 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 点\] 追加の制限はない． - - - - - - ### 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 $ の条件を満たしている．同じ地点に複数の選手がいる場合が含まれることに注意せよ．