Vito phải ngăn \(m\) zombie đi từ hang bí mật đến thành phố cách \(n\) mét. Mỗi giây có một zombie mới rời hang, và mọi zombie đang đi tiến thêm một mét; zombie vượt qua mét thứ \(n\) sẽ vào thành phố. Vito đặt \(k\) quả bom. Bom \((x,r,t)\) nổ ở thời điểm \(t\) và tiêu diệt mọi zombie còn trên đoạn đường có vị trí \(y\) thỏa \(|x-y|\le r\). Zombie đã vào thành phố hoặc còn ở trong hang không bị ảnh hưởng. Nhiều bom có thể nổ cùng lúc, kể cả tại cùng vị trí. Hãy đếm số zombie đến được thành phố.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n,m,k\le200\)). Mỗi trong \(k\) dòng tiếp theo chứa \(x,r,t\) (\(1\le x\le n\), \(0\le r\le n\), \(1\le t\le500\)), lần lượt là vị trí, bán kính và thời điểm nổ của một quả bom.

Dữ liệu ra

In số zombie đến được thành phố.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(13\) điểm: \(m=1\).
2. \(27\) điểm: \(k=1\).
3. \(10\) điểm: không có ràng buộc thêm.

Ví dụ

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

1

7 7 1
3 2 6

2

3 3 1
3 3 3

0

Nguồn

COCI 2025/2026 - Vòng 4, bài Zombie Apocalypse.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.