시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5711057922.191%

문제

정은이는 두더지 잡기 게임을 즐겨 한다. 어느 날 정은이는 한 야외 행사에서 대형 두더지 잡기 게임을 하게 되었다.

게임은 큰 벌판에서 진행되는데, 게임을 시작한 뒤 T(1 ≤ T ≤ 1,000,000,000)초가 지났을 때, 벌판의 (x, y) 좌표(0 ≤ |x|, |y| ≤ 1,000)에서 두더지가 나타나게 된다. 두더지는 매우 짧은 시간동안만 나타나므로, 정확히 T초에 그 위치에 있게 되면 그 위치에서 나타나는 두더지를 잡을 수 있다. 게임을 하기 위해서는 벌판의 이곳저곳을 돌아다녀야 하는데, 정확히 T초에 두더지가 나타나는 위치에 도착한 경우에도 두더지를 잡을 수 있는 것으로 간주한다.

이러한 두더지들이 N(1 ≤ N ≤ 6,666)마리가 있는데, 정은이는 이 두더지들을 최대한 많이 잡기 위해서 미리 계획을 세우고 이동해야 함을 알게 되었다. 게다가 정은이는 1초에 S(1 ≤ S ≤ 1,000)만큼의 거리를 움직일 수 있기 때문에, 이러한 점도 고려하여 계획을 세워야 한다. 만약 (0, 0)의 위치에서 (1, 1)의 위치로 이동해야 하고, 1초에 1만큼의 거리를 움직일 수 있다면, 대략 1.41초 정도의 시간이 필요하게 된다.

두더지들에 대한 정보가 주어졌을 때, 정은이가 잡을 수 있는 두더지의 최대 마리수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, S가 주어진다. 다음 N개의 줄에는 각 두더지에 대한 정보를 나타내는 세 정수 x, y, T가 주어진다. 게임이 시작되는 순간(T = 0)에 정은이의 위치는 (0, 0)이라고 가정한다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

1 1
1 1 2

예제 출력 1

1