27499번 - 레이저 쏘기

폭의 길이가 $M$이고 가장 아래쪽이 고정되어 있으며 위쪽으로 무한한 높이를 갖는 평면이 있다.

해당 공간을 좌표평면에 대응하면 가장 왼쪽 아래 지점이 점 $(0, 0)$에 대응된다. 그리고 점$(0,0)$에서 오른쪽으로 $x$만큼, 위쪽으로 $y$만큼 떨어진 위치가 점 $(x, y)$에 대응되며, 공간의 폭이 $M$이므로 $x = 0$과 $x = M$이 공간의 양쪽 벽에 대응된다.

점 $(0,0)$에 레이저 발사기가 하나 있다. 공간의 양쪽 벽은 전부 거울로 되어있어서 발사된 레이저가 벽에 닿으면 입사각과 반사각이 같게 반사되어 진행한다. 레이저 발사기는 벽과 평행한 방향이나 수직인 방향으로는 기술적인 문제로 돌릴 수 없다.

평면 위의 $x$, $y$가 모두 정수인 서로 다른 $N$개의 정수 점 위에 센서가 있다. 레이저가 정확히 센서가 있는 좌표를 지나가는 동안에 각 센서마다 연결된 전구에 빛이 들어온다. 하지만 거울에 닿을 때마다 레이저의 세기가 약해져서 거울에 $K$번 이상 반사된 레이저는 센서에서 인식을 못한다.

센서의 수 $N$과 각 센서의 좌표들이 주어졌을 때, 발사기의 발사 각도를 잘 조절해서 동시에 최대 몇 개의 전구를 켤 수 있는지 구해보자.

첫째 줄에 센서의 수 $N$ ($1 \le N \le 1\,000$), 벽의 폭 $M$ ($2 \le M \le 10\,000$), 레이저의 세기가 부족해지는 반사 횟수 $K$ $(1 \le K \le 1\,000)$가 주어진다. 이후 둘째 줄에서 $N + 1$째 줄까지 각 센서가 위치한 점의 좌표 $(x, y)$ $(0 < x < M,$ $0 < y < 10\,000\,000)$ $N$개가 차례대로 주어진다. 모든 센서는 정수 점 위에 존재하며 중복된 점이 들어오는 경우는 없다.

첫째 줄에 레이저 발사기로 동시에 켤 수 있는 전구의 최대 개수를 출력한다.