두더지 잡기

떠돌이 놀이공원을 구경하던 중, 갑자기 두더지 잡기 게임의 최고 점수를 깨고 싶은 충동이 든다. 두더지 잡기의 목표는 망치로 두더지를 잡는 것이다. 일을 쉽게 하기 위해 먼저 점쟁이에게 물어보았고, 이제 두더지가 나타나는 정확한 패턴을 알고 있다.

두더지는 2차원 좌표평면에서 $0 \le x, y < n$을 만족하는 $n^2$개의 정수 격자점 $(x, y)$에 있는 구멍에서 나온다. 각 시각(time step)마다 일부 두더지가 나타났다가 다음 시각이 되기 전에 다시 사라진다. 두더지가 나타난 뒤 사라지기 전에, 망치를 현재 위치 $(x_1, y_1)$에서 유클리드 거리로 최대 $d$만큼 떨어진 임의의 점 $(x_2, y_2)$까지 직선으로 움직일 수 있다. 망치는 정수 좌표를 가진 점으로만 옮길 수 있다. 두더지가 나온 구멍의 중심이 $(x_1, y_1)$과 $(x_2, y_2)$를 잇는 선분 위(양 끝점 포함)에 있으면 그 두더지를 잡은 것이다. 잡은 두더지 하나당 1점을 얻는다. 첫 번째 시각이 시작되기 전에는 망치를 원하는 아무 위치에나 놓을 수 있다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 정수 $n$, $d$, $m$이 주어지는 줄로 시작한다. 여기서 $n$과 $d$는 위에서 설명한 값이고, $m$은 나타나는 두더지의 총 개수이다 ($1 \le n \le 20$, $1 \le d \le 5$, $1 \le m \le 1000$). 이어서 $m$개의 줄이 주어지며, 각 줄에는 두더지가 나타나는 위치와 시각을 나타내는 세 정수 $x$, $y$, $t$가 있다 ($0 \le x, y < n$, $1 \le t \le 10$). 같은 위치에 같은 시각에 나타나는 두더지는 없다.

입력의 끝은 $n = d = m = 0$인 테스트 케이스로 표시되며, 이 경우는 처리하지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 얻을 수 있는 최대 점수이다.