Ở vương quốc JOI cổ đại, mỗi khi một vị vua qua đời, người ta xây một kim tự tháp trên sa mạc làm lăng mộ. Vị trí tâm và chiều cao của kim tự tháp được quyết định bằng bói toán.

Sa mạc là hình chữ nhật có chiều rộng theo hướng đông–tây là \(W\) và chiều dài theo hướng bắc–nam là \(H\), được chia thành các ô vuông \(1\times1\). Mỗi ô được biểu diễn bằng cặp số nguyên \((x,y)\) với \(0\le x<W\), \(0\le y<H\). Ô \((0,0)\) nằm ở góc tây bắc; ô \((x,y)\) nằm cách ô \((0,0)\) một khoảng \(x\) ô về phía đông và \(y\) ô về phía nam.

Một kim tự tháp có tâm tại ô \((X,Y)\) và chiều cao \(h\) yêu cầu số viên đá tại ô \((x,y)\) trong sa mạc là

Không đặt đá ở bên ngoài sa mạc. Chẳng hạn, với \(W=7\), \(H=6\), khi xây kim tự tháp có tâm \((2,1)\) và chiều cao \(3\), số viên đá ở mỗi ô như sau:

Do diện tích vương quốc có hạn, các kim tự tháp có thể chồng lên nhau. Khi xây một kim tự tháp mới yêu cầu \(n\) viên đá tại một ô:

• Nếu ô đó đã có ít nhất \(n\) viên đá thì không thay đổi gì.
• Nếu ô đó có ít hơn \(n\) viên đá thì bổ sung đá để ô đó có đúng \(n\) viên.

Ví dụ, từ trạng thái trên, nếu xây thêm kim tự tháp có tâm \((4,3)\) và chiều cao \(4\), số viên đá ở mỗi ô trở thành:

Yêu cầu

Cho vị trí tâm và chiều cao của tất cả các kim tự tháp, hãy tính tổng số viên đá cần dùng để xây chúng, với sa mạc ban đầu chưa có đá.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên \(W,H,N\), trong đó \(N\) là số kim tự tháp.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa ba số nguyên \(x_i,y_i,h_i\), mô tả kim tự tháp thứ \(i\) có tâm \((x_i,y_i)\) và chiều cao \(h_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng số viên đá cần dùng để xây tất cả các kim tự tháp.

Ràng buộc

• \(1\le W,H\le3000\).
• \(1\le N\le10\,000\).
• \(0\le x_i<W\), \(0\le y_i<H\).
• \(1\le h_i\le3000\).
• Giới hạn thời gian: \(5\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(20\) nhóm, mỗi nhóm \(5\) điểm và chứa đúng một test, lần lượt từ 01 đến 20.

• \(10\) điểm dành cho các test thỏa mãn \(W,H\le1000\) và \(N\le5\).
• \(25\) điểm dành cho các test thỏa mãn \(W,H\le500\) và chiều cao của mọi kim tự tháp không vượt quá \(100\).

Ví dụ

7 6 2
2 1 3
4 3 4

81

3000 3000 1
1500 1500 3000

17999999500