009 - 忍ぶべし

あなたにはあるミッションが課せられている．それは，無限に広がる二次元グリッド上にある降下地点マス (sx, sy) へと人員を送り込み，その後敵陣に悟られることがないよう移動をサポートし，敵の基地があるマス (gx, gy) への潜入を成功させることだ．あなたはこの重要なミッションの潜入役を，忍び込みのプロ・忍小宮に託した．

忍小宮は上下左右の隣接した 4 マスのいずれかに移動することを繰り返し，敵の基地を目指す．また，迅速に任務を遂行するため，降下地点から敵の基地まで必ず最短距離となるよう移動を行う．

事前の偵察によるとこの 2 次元グリッド上には敵のセンサーが N 個あり，i 番目のセンサーは (x_i, y_i) を中心として 1 辺 2r_i + 1 の正方形領域，すなわち |x - x_i| ≤ r_i かつ |y - y_i| ≤ r_i を満たすような全てのマス (x, y) をカバーしていることがわかっている．忍小宮は 1 つ以上のセンサーにカバーされている領域に入ると敵に発見されてしまう．

ここで問題になるのは，現在のセンサーの配置ではどうしても忍小宮が最短距離の移動で敵の基地まで辿り着けない可能性があることだ．この場合，あなたはサポート役としてセンサーを破壊しなければならない．リスク・コストを軽減するため，破壊するセンサーの個数はできる限り少なくしたい．

例として，入力サンプルの 4 番目のデータセットは図 C-1 のようになる．図 C-2 のように 3 つのセンサーを取り除くことにより，忍小宮は最短距離で敵の基地まで辿り着くことができるようになり，この例ではこれが最小個数である．

勘のいいあなたはお気付きだろう．どうしてもセンサーに検知されてしまう忍小宮より，センサーに検知されずに破壊できるあなたの方が，忍び込みスキルが高いということに．そう，何を隠そう忍小宮は自分を忍び込みのプロだと勘違いしているだけのただの一般人であり，あなたこそが忍び込ませのプロ・忍駒瀬だったのだ．何も知らない忍小宮には気付かれず密やかに必要最低限のセンサーを破壊し，あたかも自分は忍び込みのプロなのだと忍小宮に思い込ませることが，忍び込ませのプロとしてのあなたの矜恃だ．まずはプロとしてあらかじめコストを見積もるため，忍小宮の任務を成功させるには最小でいくつのセンサーを破壊する必要があるか求めて欲しい．

入力は 100 個以下のデータセットからなる． 各データセットは次の形式で表される．

N sx sy gx gy x₁ y₁ r₁ ... x_N y_N r_N

最初の行はセンサーの個数 N (1 ≤ N ≤ 10⁵) を表す整数からなる． 2 行目の sx, sy は忍小宮の降下地点 (sx, sy) を，gx, gy は敵の基地の位置 (gx, gy) をそれぞれ表し，1 ≤ sx, gx ≤ 1000，1 ≤ sy, gy ≤ 1000 を満たす． 続く N 行の i 行目は i 番目のセンサーの情報であり，センサーが位置 (x_i, y_i) を中心に 1 辺 2r_i +1 の正方形領域をカバーしていることを表す．1 ≤ x_i ≤ 1000，1 ≤ y_i ≤ 1000，0 ≤ r_i ≤ 1000 をそれぞれ満たす． ここで，(sx, sy) と (gx, gy) は必ず異なるマスである．

入力の終わりは 1 つのゼロからなる行で表される．

各データセットについて，忍小宮が (sx, sy) から (gx, gy) までセンサー領域を通らず最短距離で移動できるようにするために破壊する必要があるセンサーの最小個数を 1 行に出力せよ．

3
2 2 4 5
1 1 1
1 5 2
4 3 1
5
1 2 1 1
5 3 2
8 8 6
6 9 2
1 7 3
4 4 1
1
3 7 1 1
2 5 10
9
25 30 90 100
50 50 15
60 30 20
70 35 15
90 50 10
80 70 20
65 85 15
40 70 35
25 55 20
25 80 20
0

2
0
1
3