Starry Sky(星空) - joi2009-day4

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 3秒

メモリ制限: 256MB

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

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

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

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

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

Input.

入力ファイルstarry_sky.inの1行目には, 星の数を表す整数N(1 ≤ N ≤ 4000) が書かれている.

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

Output.

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

採点基準

採点用データのうち, 配点の15% 分についてはN ≤ 100, 配点の25% 分についてはN ≤ 400, 配点の35% 分についてはN ≤ 700, 配点の50% 分についてはN ≤ 1000 を満たす.

また, 配点の20% 分についてはx[i], y[i], L[i] ≤ 1000 を満たす.

例1

starry_sky.in 標準出力
4
1 2 6
4 3 3
3 1 4
5 5 2		 3

例2

starry_sky.in 標準出力
5
11 6 7
12 13 8
15 16 18
2 2 13
3 4 11		 2