Vito đang nghiện trò chơi điện tử mới nổi ~Zombie Apocalypse~. Hiện tại cậu phải đối mặt với thử thách sau: có ~m~ con zombie đang tiến về phía thành phố, và nếu không ngăn lại thì chúng sẽ tấn công thành phố.

Cụ thể hơn, đám zombie xuất phát từ một hang bí mật cách thành phố ~n~ mét và rời hang lần lượt từng con một. Mỗi zombie di chuyển về phía thành phố với vận tốc ~1~ mét mỗi giây, và giữa hai lần zombie liên tiếp rời hang luôn có đúng ~1~ giây nghỉ.

Vì vậy, sau giây thứ ~1~ sẽ có ~1~ zombie cách hang ~1~ mét; sau giây thứ ~2~ sẽ có các zombie ở vị trí ~1~ và ~2~ mét; sau giây thứ ~3~ sẽ có các zombie ở vị trí ~1~, ~2~, ~3~ mét; v.v. Mỗi khi một zombie đi qua cột mốc ~n~, nó sẽ tới được thành phố.

Theo luật của trò chơi, Vito được phép thả ~k~ quả bom trên đoạn đường từ hang tới thành phố để ngăn cuộc tấn công. Với mỗi quả bom, cậu có thể tùy ý chọn:

• vị trí thả bom, tức khoảng cách từ hang,
• bán kính của quả bom,
• thời điểm thả bom, tính bằng giây.

Một quả bom bán kính ~r~ được thả tại vị trí ~x~ vào thời điểm ~t~ sẽ tiêu diệt một zombie nếu tại đúng thời điểm đó zombie đang ở vị trí ~y~ sao cho ~|x - y| \le r~. Những zombie đã tới thành phố rồi sẽ không bị ảnh hưởng bởi bom. Một khi đã bị tiêu diệt, zombie đó sẽ không thể tiếp tục di chuyển nữa.

Vito có thể chọn vị trí, bán kính và thời điểm thả bom một cách hoàn toàn tự do; nhiều quả bom cũng có thể nổ cùng lúc, thậm chí ở cùng một vị trí.

Biết toàn bộ lựa chọn của Vito cho ~k~ quả bom, hãy xác định có bao nhiêu zombie sẽ tới được thành phố.

Input

Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~: độ dài đoạn đường từ hang tới thành phố, số lượng zombie và số lượng bom.

Mỗi trong ~k~ dòng tiếp theo chứa ba số nguyên dương ~x~, ~r~, ~t~: vị trí thả bom, bán kính của quả bom và thời điểm thả bom.

Output

In ra trên một dòng duy nhất số lượng zombie đã tới được thành phố.

Ràng buộc

• ~1 \le n, m, k \le 200~
• ~1 \le x \le n~
• ~0 \le r \le n~
• ~1 \le t \le 500~

Chấm điểm

• Subtask 1 (13 điểm): ~m = 1~
• Subtask 2 (27 điểm): ~k = 1~
• Subtask 4 (30 điểm): Không có ràng buộc bổ sung.

Sample Input 1

6 3 3
3 1 2
5 0 7
4 4 8

Sample Output 1

1

Sample Input 2

7 7 1
3 2 6

Sample Output 2

2

Sample Input 3

3 3 1
3 3 3

Sample Output 3

0

Giải thích

• Ví dụ 1: Sau khi xét cả ~3~ quả bom, chỉ còn đúng ~1~ zombie tới được thành phố.