While visiting a traveling fun fair you suddenly have an urge to break the high score in the Whac-a-Mole game. The goal of the Whac-a-Mole game is to... well... whack moles. With a hammer. To make the job easier you have first consulted the fortune teller and now you know the exact appearance patterns of the moles. The moles appear out of holes occupying the n² integer points (x, y) satisfying 0 ≤ x, y <n in="" a="" two-dimensional="" coordinate="" system.="" at="" each="" time="" step,="" some="" moles="" will="" appear="" and="" then="" disappear="" again="" before="" the="" next="" step.="" after="" but="" they="" disappear,="" you="" are="" able="" to="" move="" your="" hammer="" straight="" line="" any="" position="" (x2="" ,="" y2="" )="" that="" is="" distance="" most="" d="" from="" current="" (x1="" y1="" ).="" for="" simplicity,="" we="" assume="" yo="" can="" only="" point="" having="" integer="" coordinates.="" mole="" whacked="" if="" center="" of="" hole="" it="" appears="" out="" located="" on="" between="" an="" (including="" two="" endpoints).="" every="" earns="" point.="" when="" game="" starts,="" first="" place="" anywhere="" see="" fit.="" Input

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 ≤ n ≤ 20, 1 ≤ d ≤ 5, and 1 ≤ m ≤ 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 ≤ x, y < n and 1 ≤ t ≤ 10). No two moles will appear at the same place at the same time. The input is ended with a test case where n = d = m = 0. This case should not be processed.

Output

For each test case output a single line containing a single integer, the maximum possible score achievable.

Example

Input:
4 2 6
0 0 1
3 1 3
0 1 2
0 2 2
1 0 2
2 0 2
5 4 3
0 0 1
1 2 1
2 4 1
0 0 0

Output:
4
2