题目描述
When summer comes to the farm, it is time to harvest the cow's favorite fruit, apples. At FJ's farm, they have an extraordinary way of harvesting apples: Bessie shakes an apple tree, the apples fall down and FJ tries to catch as many of the N (1 <= N <= 5,000) apples as possible.
As an experienced apple catcher, FJ plots his apple catching carefully. He knows exactly where (an X,Y coordinate where each of X and Y is in the range -1,000..1,000) each apple will fall and when (a time in the range 1 <= T <= 1,000,000). He walks to his planned apple-catching spot so that he can catch the apple as it falls.
FJ can walk S (1 <= S <= 1,000) units per unit of time. What is the greatest number of apples he can catch if he starts at point (0,0) at time 0? Note that FJ takes just over 1.41 units of time to walk from (0,0) to (1,1) when walking at speed 1.
输入
* Line 1: Two space-separated integers: N and S
* Lines 2..N+1: Line i+1 contains the cartesian coordinates and time apple i lands with three space-separated integers: X_i, Y_i, and T_i
输出
* Line 1: A file with a single line containing an integer that is the largest possible number of apples that FJ can catch.
5 3
0 0 1
0 3 2
-5 12 6
-1 0 3
-1 1 2
提示
OUTPUT DETAILS:
FJ can catch apples 1, 5 and 4.