009 - ホモノハザード

時間制限 1 秒 / メモリ制限 64 MB / 得点 17 / x 0 /


TLE
1sec
MLE
64MB
得点
17

もんだい

2056年 1月1日、世界のゲーマーたちが待望していたあるゲームの発売日である。

その名も 「ホモノハザード」 !!

このゲームは、W(横)×H(縦)に、N体の「HOMONO」がいる。

この「HOMONO」は次のような動きをする。

  • 上下左右の4方向に進むことができる。
  • 他の「HOMONO」もしくは壁にぶつかるまで進み続ける。
  • 他の「HOMONO」にびつかったとき、「HOMONO」は1体に結合し、その場にとどまる。

※「HOMONO」の上のような動きを1回とカウントする。

このゲームは、「HOMONO」を残り1体にするために必要な「HOMONO」を動かす回数を最小にして動かすことでクリアとなる。


あるところに住む少年こものくんは「ホモノハザード」の世界トッププレイヤーを目指している。

しかし、こものくんはおばかなので、最小回数を効率よく求めることができませんでした。

そこで、こものさんはプログラマーであるあなたを雇い、「ホモノハザード」をクリアするための最小回数を求めるように要求してきました。

ステージ(盤面)の様子とゾンビの初期位置が与えられたとき、残りのゾンビを1体にするための最小回数を求めるプログラムを作成してください。

入力

N W H
xi yi

1 行目に3つの整数 N,W,H が空白区切りで与えられる。

2 行目からN+1 行目に2つの整数 xi,yi が空白区切りで与えられる。

出力

「HOMONO」が1体になるためにかかる時間(ターン)の最小値を求めて1行に出力する。

制約

全ての入出力ケースについて以下を満たす。

  • 2 ≦ N ≦ 100000
  • 1 ≦ W, H ≦ 200000
  • 1 ≦ xiW
  • 1 ≦ yiH

入出力例

入力例1

4 3 3
1 1
1 3
3 1
3 3

出力例1

3

入力例2

2 3 3
2 2
3 3

出力例2

2

入力例3

2 4 4
2 2
3 3

出力例3

3

入力例4

2 4 4
2 2
2 3

出力例4

1

入力例5

7 6 6
1 1
1 6
3 2
3 4
4 5
5 2
6 4

出力例

8

解説

今回のテストケースはこのように「HOMONO」を動かす。