004 - 毒の沼地

時間制限 8 秒 / メモリ制限 256 MB / 得点 20 / x 2 /


TLE
8sec
MLE
256MB
得点
20

問題

あなたはレトロなロールプレイングゲームで遊んでいる.このゲームのフィールドは縦 100 マス,横 100 マスのマス目状である.このフィールドの左から x 列目,上から y 行目のマスは (x, y) と表される.あなたが操作するキャラクターはフィールド内のいずれかのマスの上におり,フィールド内を上下左右に 1 マスずつ移動することができる.

あなたが操作するキャラクターはいま (X0, Y0) にいて,これから N 箇所の目的地を順番に訪問する予定である.しかしながら,あなたはキャラクターを操作するとき,フィールドのマスの種類に注意してキャラクターを移動させなければならない.それぞれのマスは毒のある沼地か毒のない土地のどちらかである.キャラクターの移動先のマスが毒のある沼地の場合にはキャラクターはダメージを受け,移動先のマスが毒のない土地の場合にはダメージを受けない.あなたはキャラクターへのダメージを減らすため,適切に経路を選ぶことでキャラクターがダメージを受ける回数をできるだけ少なくしたい.ダメージの有無はキャラクターの移動先のマスの種類で決まること,例として,移動元のマスが毒のある沼地で移動先のマスが毒のない土地の場合にはキャラクターはダメージを受けないことに注意せよ.

あなたの分析によれば,左上を (A, B) ,右下を (C, D) とする長方形の範囲内のマスは毒のない土地であり,それ以外のマスは毒のある沼地である.あなたのキャラクターが毒のある沼地からダメージを受ける回数を最小化するように N 箇所の目的地を順番に訪問したとき,あなたの操作するキャラクターがダメージを受ける回数を求めよ.

Input

入力は最大で 50 個のデータセットからなる. 各データセットは次の形式で表される.

N A B C D X0 Y0 X1 Y1 X2 Y2 ... XN YN

データセットは N+3 行からなる.

1 行目は目的地の数 N (1 ≤ N ≤ 100) を表す整数である.

2 行目は毒のない土地となっている長方形の範囲を表す整数 ABCD であり,1 ≤ A ≤ C ≤ 1001 ≤ B ≤ D ≤ 100 を満たす.キャラクターの移動先のマス (x, y)A ≤ x ≤ CB ≤ y ≤ D を満たすとき,またその場合に限りキャラクターはダメージを受けない.

3 行目はあなたが操作するキャラクターが最初にいるマスの座標 (X0, Y0) を表す整数であり 1 ≤ X0, Y0 ≤ 100 を満たす.4 行目から続く N 行には N 箇所の目的地の座標が与えられる.3+i 行目は i 番目の目的地のマスの座標 (Xi, Yi) を表す整数であり 1 ≤ Xi, Yi ≤ 100 を満たす.キャラクターが最初にいるマスおよび目的地のマスの座標はそれぞれ異なる,すなわち (Xj, Yj) ≠ (Xk, Yk) (0 ≤ j < k ≤ N) を満たす.

入力の終わりは,1 個のゼロだけからなる行で表される.

Output

各データセットについて,あなたの操作するキャラクターがダメージを受ける回数を 1 行で出力せよ.

Sample Input

2
3 3 5 7
3 3
7 3
7 7
5
1 10 100 10
1 1
100 1
50 20
50 80
51 21
51 1
0

Output for the Sample Input

5
174

入力例を以下の図に示す.(3, 3) から (5, 3) の間は毒のない土地であるが (6, 3)(7, 3) は毒のある沼地であるため,1 番目の目的地に移動するまでにダメージを 2 回受ける.1 番目の目的地から 2 番目の目的地まで下方向に 4 回移動して最短距離で移動した場合は,すべてのマスが毒のある沼地であるためダメージを 4 回受ける.遠回りして毒のない土地を通った場合は,(6, 3)(6, 7)(7, 7) の毒のある沼地に入るためダメージを 3 回受ける.ダメージを受ける回数を最小化するような移動方法を選んだとき,ダメージを受ける回数は 5 回である.