Soccer

Time Limit : 3 sec, Memory Limit : 262144 KB

サッカー(Soccer)

あなたはJOI リーグの名門サッカークラブに所属するマネージャーである.

クラブには $N$ 人の選手が所属しており,選手には1 から $N$ までの番号が付けられている.選手たちは優勝を目指してグラウンドで日々練習をしている.グラウンドは縦 $H$ メートル,横 $W$ メートルの長方形の形状をしている.グラウンドの縦方向は南北方向に平行であり,横方向は東西方向に平行である.グラウンドの北西隅から南に $i$ メートル,東に $j$ メートル進んだ地点を地点 $(i, j)$ と呼ぶことにする.

練習が終わったあと,練習に使用したボールを片付けなければならない.片付け開始時点では,選手 $i$ ($1 \leq i \leq 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$ メートルの長方形の形状をしていることを表している.
  • 2 行目には疲労度の増加に関する3 個の整数 $A, B, C$ が空白を区切りとして書かれている.
  • 3 行目には整数 $N$ が書かれている.これは選手が $N$ 人いることを表している.
  • 続く $N$ 行のうち $i$ 行目($1 \leq i \leq N$) には2 つの整数 $S_i, T_i$ が空白を区切りとして書かれている.これらは片付け開始時点で選手 $i$ が地点 $(S_i, T_i)$ にいることを表している.

出力

標準出力に,片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を1 行で出力せよ.

制限

すべての入力データは以下の条件を満たす.

  • $1 \leq H \leq 500.$
  • $1 \leq W \leq 500.$
  • $0 \leq A \leq 1 000 000 000.$
  • $0 \leq B \leq 1 000 000 000.$
  • $0 \leq C \leq 1 000 000 000.$
  • $2 \leq N \leq 100 000.$
  • $0 \leq S_i \leq H (1 \leq i \leq N).$
  • $0 \leq T_i \leq W (1 \leq i \leq N).$
  • $(S_1, T_1) \ne (S_N, T_N).$

入出力例

入力例1

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

出力例1

26

この入力例では,グラウンドは下図の状態となっている.図において,白い丸は選手を,黒い丸はボールを表している.あなたは(6, 5) にいる.


グラウンドの初期状態

この場合,以下のように行動すればよい.

  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$ となり,これが最小値となる.


最適解における行動の様子

入力例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

同じ地点に複数の選手がいる場合が含まれることに注意せよ.



Source: 16th Japanese Olympiad in Informatics , 2016-2-11
http://www.ioi-jp.org/