D問題 - Chessroom

実行時間制限: 2sec / メモリ制限: 1024MB

問題文

教室の床は、縦\(H\)枚、横\(W\)枚の正方形のタイルでぴったり敷き詰められています。ここで、前から\(i\)番目、左から\(j\)番目のタイルを\((i,j)\)と表すこととします。

はじめ、タイルの上には何も置かれていません。

そーだくんはチェスの駒と旗をたくさん持っています。ここで、そーだくんはチェスの駒をいくつか取り出し、1個のナイトを\((x,y)\)に置き、\(N\)個のポーンのうち、\(k\)番目のポーンを\((a_k,b_k)\)に置きました。

その後、そーだくんは一回の操作ごとに、以下のどちらか一つの行動をとります。

• ナイトをタイルのいずれかに移動させる。ただし、タイルが存在しない場所や、既にポーンが置かれているタイルに移動させることはできない。
• ナイトがいるタイルに旗を置く。その後、ナイトを最初に置いた位置、つまり\((x,y)\)に移動させる。

なお、旗を置く場合、ナイトを最初に置いた位置まで移動させるまでを1手として扱う事に注意してください(出力例1を参照)。

そーだくんはこの操作を好きな回数だけ行う事ができます。 この時、そーだくんが最も効率よく操作した場合、全てのタイルに旗またはポーンが置かれている状態にするためには、最低何回の操作が必要でしょうか。

制約

• \(1 \leq H, W \leq 1000\)
• \(0 \leq N < HW\)
• \(1 \leq x, a_k \leq H\)
• \(1 \leq y, b_k \leq W\)
• \((a_k, b_k)\), \((x,y)\)は相異なる。
• 入力は全て整数で与えられる。

入力

入力は以下の形式で標準入力から与えられる。

H W
x y
N
a1 b1
a2 b2
:
aN bN

出力

• 問題文に対する答えを整数で出力せよ。
• ただし、そーだくんがどのように操作しても全てのタイルに旗またはポーンが置かれている状態にできない場合は、-1を出力せよ。

入力例1

3 3
1 3
6
1 2
2 1
2 2
2 3
3 1
3 3

出力例1

6

• 1回目の操作でナイトを(1,3)から(3,2)へ移動させる。
• 2回目の操作でナイトを(3,2)から(1,1)へ移動させる。
• 3回目の操作で(1,1)に旗を置き、ナイトを(1,3)へ移動させる。
• 4回目の操作でナイトを(1,3)から(3,2)へ移動させる。
• 5回目の操作で(3,2)に旗を置き、ナイトを(1,3)へ移動させる。
• 6回目の操作で(1,3)に旗を置く。

例えばこのように操作することで、最小の手数で全てのタイルに旗またはポーンが置かれている状態にできます。 6手が最小の手数となるため、6を出力します。

入力例2

5 5
3 3
8
1 2
1 4
2 1
2 5
4 1
4 5
5 2
5 4

出力例2

-1

そーだくんがどのように操作しても、全てのタイルに旗またはポーンが置かれている状態にできません。したがって、-1を出力します。

入力例3

3 3
2 2
8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3

出力例3

1

ナイトを最初に置いたタイルに旗を置くだけでよいので、1を出力します。

入力例4

9 9
5 5
0

出力例4

281

ポーンが1個も置かれていない場合もあります。