📖 Bài giảng & lời giải: đây là Bài tập 5 trong bài giảng Chuyên đề nhập môn 9: Cộng dồn 2 chiều trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một vùng đất được chia thành bảng gồm $n$ hàng, $m$ cột ô. Có $k$ trạm phát sóng, trạm thứ $t$ đặt ở ô $(x_t, y_t)$ (hàng $x_t$, cột $y_t$) với bán kính $r_t$, phủ sóng mọi ô $(i, j)$ trong bảng thoả $|i - x_t| \le r_t$ và $|j - y_t| \le r_t$. Nhiều trạm có thể đặt cùng một ô.

Hãy cho biết số ô không có sóng (không được trạm nào phủ), và số trạm lớn nhất cùng phủ lên một ô.

Dữ liệu vào

• Dòng 1: ba số nguyên $n, m, k$ ($1 \le n, m \le 1000$, $1 \le k \le 10^5$).
• $k$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $x, y, r$ ($1 \le x \le n$, $1 \le y \le m$, $0 \le r \le 2000$) mô tả một trạm.

Kết quả

• Dòng 1: số ô không có sóng.
• Dòng 2: số trạm lớn nhất cùng phủ lên một ô.

Sample Input

5 6 2
2 2 1
3 4 1

Sample Output

14
2