Whac-a-Mole

While visiting a traveling fun fair you suddenly get the urge to beat the high score in the Whac-a-Mole game. The goal of Whac-a-Mole is to whack moles with a hammer. To make the job easier you have first consulted a fortune teller, and now you know the exact pattern in which the moles will appear.

The moles come out of holes located at the $n^2$ integer points $(x, y)$ satisfying $0 \le x, y < n$ in a two-dimensional coordinate system. At each time step some moles appear and then disappear again before the next time step. After the moles appear but before they disappear, you may move your hammer in a straight line to any point $(x_2, y_2)$ that is at Euclidean distance at most $d$ from its current position $(x_1, y_1)$. The hammer may only be moved to points with integer coordinates. A mole is whacked if the center of the hole it came out of lies on the segment between $(x_1, y_1)$ and $(x_2, y_2)$ (both endpoints included). Each whacked mole earns you one point. Before the first time step, you may place your hammer at any position you like.

The input consists of several test cases. Each test case starts with a line containing three integers $n$, $d$ and $m$, where $n$ and $d$ are as described above and $m$ is the total number of moles that will appear ($1 \le n \le 20$, $1 \le d \le 5$, and $1 \le m \le 1000$). Then follow $m$ lines, each containing three integers $x$, $y$ and $t$ giving the position and time of the appearance of a mole ($0 \le x, y < n$ and $1 \le t \le 10$). No two moles will appear at the same place at the same time.

The input ends with a test case where $n = d = m = 0$; this case must not be processed.

For each test case, output a single line containing one integer: the maximum score you can achieve.