Xe buýt

View as PDF

Submit solution


Points: 0.41 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
POI 2005
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 độ (~x_i~, ~y_i~) và có ~z_i~ 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.

Input

  • Dòng đầu ghi ~3~ số nguyên dương ~X~, ~Y~, ~N~ (~X~, ~Y~ ~\leq~ ~10^9~, ~N \leq 10^5~)
  • ~N~ dòng sau mỗi dòng ghi ~3~ số ~x_i~, ~y_i~, ~z_i~ (~x_i \le X~, ~y_i \le Y~, ~z_i \leq 10^6~).

Output

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

Sample Input

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

Sample Output

11

Comments

Please read the guidelines before commenting.


There are no comments at the moment.