009 - ホモノハザード

もんだい

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つの整数 x_i,y_i が空白区切りで与えられる。

出力

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

制約

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

• 2 ≦ N ≦ 100000
• 1 ≦ W, H ≦ 200000
• 1 ≦ x_i ≦ W
• 1 ≦ y_i ≦ H

---

入出力例

入力例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」を動かす。