← 返回题目列表

Codeforces · 420/E

E. 打球

中文机器翻译题面 查看原题

编码员不能整天坐着编码。有时从办公桌上站起来休息一下、与同事闲聊甚至玩耍是个好主意。 F公司的程序员们有他们最喜欢的球类运动。

让我们想象一下在笛卡尔坐标系的平面上进行的游戏。点 (0, 0) 包含选择任意方向并向该方向扔球的玩家。球击中距离玩家原始位置 d 处的平面,并继续沿同一方向飞行。球第一次撞击平面后,它会继续飞行并在距离玩家原始位置 2·d 处再次撞击平面,依此类推(继续沿所选方向飞行并在每 d 个单位后撞击平面)。 F连的编码员个个实力都很强,所以球飞得无限​​远。

平面上画有 n 个圆圈。如果球击中平面并击中平面上绘制的圆圈(包括其边界),则玩家获得一分。球可以一次击中多个圆圈,每个圆圈获得一分(如果球在移动过程中击中某个圆圈 x 次,则玩家也获得 x 分)。计算玩家向任意方向扔球时可以获得的最大分数。请注意,方向可能具有实际坐标。

输入

第一行包含两个以空格分隔的整数 — n и d (1 ≤ n ≤ 2·104; 5 ≤ d ≤ 10)。接下来的 n 行包含圆圈的描述。第 i 行包含三个空格分隔的整数 xi、yi、r​​i (- 10000 ≤ xi, yi ≤ 10000; 1 ≤ r ≤ 50),其中 (xi, yi, ri) 分别是圆心和半径的坐标。点 (0, 0) 不在某个圆的内部或边界上。

输出

打印一个整数 - 您可以获得的最大点数。

示例

输入 #1

2 5
1 1 1
5 0 1

输出 #1

1

输入 #2

2 5
4 0 3
5 3 1

输出 #2

2

输入 #3

1 10
20 0 10

输出 #3

3