24138번 - 星空 (Starry Sky) 다국어

JOI(Japan Observatory Institution:日本天文台協会) は，最近，高性能な天体望遠鏡を設置し た．JOI は，この天体望遠鏡の性能を広く一般にアピールすることで，JOI の知名度向上につ なげようと考えている．長い会議の結果，この天体望遠鏡の性能をアピールするもっとも効果 的な宣伝方法は，十分に輝いている星ができる限り沢山映った画像を撮影し，広く一般に公開 することであるという結論に至った．

しかし，宇宙は広大である．1 枚の画像の中に全てを収めようとすれば，一つ一つの星の輝き を十分に表すことができない．

一方，この天体望遠鏡は高性能である．拡大して星空を撮影することで，各星が十分に輝い た状態として撮影することができる．ただし，拡大することで，画像の中に収めることができ る星の数が減ってしまう．最大で，いくつの十分に輝く星を画像の中に収めることができるだ ろうか．

各星に関する次の情報が与えられたときに，十分に輝いた星として画像の中に収めることが できる星の最大数を求めるプログラムを作成せよ．

• 星の位置は，x 座標と y 座標からなる 2 次元座標として与えられる．
• この天体望遠鏡で撮影できる画像は，各辺が x 軸か y 軸に平行な任意の大きさの正方形で ある．星の光度と十分に輝いた状態になるまでに必要な拡大倍率の関係を表すために，星 毎に，十分に輝いた状態で撮影するために必要となる正方形領域の一辺の長さ L が与え られる．撮影する正方形領域の一辺の長さが L 以下でなければ，画像の中にその星が入っ ていたとしても十分に輝いた星として撮影することができない．正方形領域の辺上に星が あったとしても，十分に輝いている状態の星であれば，その星は画像の中に入っていると して数えることに注意せよ．

ただし，どの異なった 2 つの星も，互いの x 座標，互いの y 座標，互いの L の値のどれも一 致することが無い．

入力の 1 行目には，星の数を表す整数 N(1 5 N 5 4000) が 書かれている．

続く N 行は星のデータを表す．i + 1 行目 (1 ≤ i ≤ N) には 3 つの整数 x_i, y_i, L_i(0 ≤ x_i ≤ 10⁹, 0 ≤ y_i ≤ 10⁹, 1 ≤ L_i ≤ 10⁹) が空白を区切りとして書かれている．これは，星の x 座標，y 座標，十分に輝いている状態として撮影できる正方形領域の一辺の長さの最大値を表す．

出力は，標準出力に行うこと．十分に輝いている状態として撮影できる星の数の最 大数を表す整数を，1 行で出力せよ．