Программист не может постоянно сидеть за компьютером и писать код. Иногда полезно отойти от рабочего места, чтобы развеяться, пообщаться с коллегами или даже поиграть. У программистов компании F есть своя любимая игра с мячом.
Представим себе эту игру на плоскости с декартовой системой координат. В точке (0, 0) плоскости стоит игрок, который выбирает произвольное направление и кидает мяч вдоль этого направления. Мяч ударяется о плоскость на расстоянии d от начальной позиции игрока и продолжает лететь в том же направлении. После первого удара мяч повторно ударяется о плоскость на расстоянии 2·d от начальной позиции игрока и так далее (продолжает лететь по направлению и ударяться через каждые пройденные d единиц расстояния). В компании F все программисты сильные, поэтому мяч улетает бесконечно далеко.
На плоскости нарисовано n кругов-мишеней. Если мяч при ударе о плоскость попадает в какой-то круг (попадание в границу также считается), то игрок получает одно очко. Мяч может попасть сразу в несколько кругов, за каждый из них будет добавлено по одному очку (если мяч попал x раз в один и тот же круг, игрок также получает x очков). Посчитайте максимальное количество очков, которое можно получить, бросив мяч в произвольном направлении. Обратите внимание, что это направление не обязательно будет выражаться целыми координатами.
В первой строке через пробел заданы два целых числа n и d (1 ≤ n ≤ 2·104; 5 ≤ d ≤ 10). Далее в n строках задано описание кругов. В i-й строке через пробел заданы три целых числа xi, yi, ri ( - 10000 ≤ xi, yi ≤ 10000; 1 ≤ r ≤ 50), где (xi, yi, ri) — координаты центра и радиус круга соответственно.
Гарантируется, что точка (0, 0) не содержится внутри или на границе какого-то из кругов.
Выведите единственное число — максимальное количество очков, которое можно получить.
2 5
1 1 1
5 0 1
1
2 5
4 0 3
5 3 1
2
1 10
20 0 10
3
Название |
---|