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

Trên mặt phẳng tọa độ cho N điểm là N trạm xe buýt, ở trạm thứ i có tọa độ (xi, yi) và có zi người đang chờ ở đó. Cần đi xe buýt từ (1, 1) đến (X, Y) sao cho đón được nhiều người nhất có thể, biết rằng xe buýt chỉ có thể đi lên trên hoặc sang phải.

Dữ liệu

• Dòng đầu ghi 3 số nguyên dương X, Y, N (X, Y < 1000000001, N < 100001)
• N dòng sau mỗi dòng ghi 3 số xi, yi, zi (xi <= X, yi <= Y, zi < 1000001).

Kết qủa

Ghi trên một dòng số duy nhất là số khách lớn nhất có thể đón được.

Ví dụ

 
Dữ liệu: 
8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
Kết qủa 
11