Giải bài trực tuyến

Ở một phiên chợ dành cho thiếu nhi có một trò chơi rất hấp dẫn với những con chuột trong một cái bàn. Nhiệm vụ của người chơi là phải làm bị thương những con chuột, càng nhiều càng tốt với một chiếc búa. Để làm cho trò chơi dễ dàng hơn, các bạn nhỏ đã hỏi bụt để biết được vị trí cũng như thời gian chính xác mà mỗi con chuột xuất hiện.

Coi mặt phẳng của mặt bàn là một hệ tọa độ Đề-các, mỗi con chuột sẽ xuất hiện từ một lỗ thủng trên mặt bàn với tọa độ nguyên (x,y) thỏa mãn 0 ≤ x, y ≤ N. Trong mỗi thời điểm, một vài con chuột sẽ xuất hiện ở những lỗ thủng khác nhau và sau đó lại chui xuống vào trước thời điểm tiếp theo. Ngay sau khi các con chuột xuất hiện và ngay trước lúc chúng biến mất, người chơi có thể di chuyển chiếc búa trên một đoạn thẳng có chiều dài tối đa là D. Để đơn giản, tọa độ của chiếc búa trước và sau khi di chuyển luôn là nguyên và coi kích thước của chiếc búa không đáng kể. Một con chuột sẽ bị thương nếu tâm của lỗ mà con chuột xuất hiện nằm trên đoạn thẳng chiếc búa di chuyển. Khi bắt đầu trò chơi, ngay trước thời điểm đầu tiên mà những con chuột xuất hiện, người chơi có thể đặt búa ở bất cứ vị trí nào.

Hãy giúp các em thiếu nhi làm bị thương nhiều chuột nhất có thể, để các em được những phần quà của ban tổ chức. Và tất nhiên ai giúp đỡ các em thiếu nhi nhiều nhất cũng sẽ có phần thưởng là điểm số trong tuần thi này.

Input

Dòng đầu ghi 3 số N, D, M trong đó M là số con chuột.

M dòng tiếp theo mỗi dòng ghi 3 số lần lượt là tọa độ và thời điểm mà mỗi con chuột xuất hiện.

Output

Xuất ra một số duy nhất là số chuột lớn nhất có thể làm bị thương.

Example

Input:
4 5 4
0 0 1
1 0 1
0 1 2
1 2 2

Output:
4

Giải thích:
Đầu tiên búa ở 1 0.
Bước 1 đập 2 con chuột ở 1 0, 0 0, rồi đưa búa tiếp đến -1 0.
Bước 2 đập 2 con chuột ở 0 1, 1 2.


Giới hạn:
1 ≤ N ≤ 20
1 ≤ D ≤ 5
1 ≤ M ≤ 1000
Thời điểm mà mỗi con chuột xuất hiện là số tự nhiên không lớn hơn 10.