시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 210 51 39 24.074%

문제

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

게임은 큰 벌판에서 진행되는데, 게임을 시작한 뒤 T(1≤T≤1,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 2

예제 출력

1

힌트