

 Task: The BusThe streets of Byte City form a regular, chessboardlike network  they are either northsouth or westeast directed. We shall call them NS and WEstreets. Furthermore, each street crosses the whole city. Every NSstreet intersects every WE one and vice versa. The NSstreets are numbered from 1 to n, starting from the westernmost. The WEstreets are numbered from 1 to m, beginning with the southernmost. Each intersection of the ith NSstreet with the jth WEstreet is denoted by a pair of numbers (i, j) (for 1 <= i <= n, 1 <= j <= m). There is a bus line in Byte City, with intersections serving as bus stops. The bus begins its itinerary by the (1, 1) intersection, and finishes by the (n, m) intersection. Moreover, the bus may only travel in the eastern and/or northern direction. There are passengers awaiting the bus by some of the intersections. The bus driver wants to choose his route in a way that allows him to take as many of them as possible. (We shall make an assumption that the interior of the bus is spacious enough to take all of the awaiting passengers, regardless of the route chosen.)
TaskWrite a programme which:
InputThe first line of the standard input contains three positive integers n, m and k  denoting the number of NSstreets, the number of WEstreets and the number of intersections by which the passengers await the bus, respectively. ( 1 <= n <= 10^{9}, 1 <= m <= 10^{9}, 1 <= k <= 10^{5}).The following k lines describe the deployment of passengers awaiting the bus, a single line per intersection. In the i + 1st line there are three positive integers x_{i}, y_{i} and p_{i}, separated by single spaces, 1 <= x_{i} <= n, 1 <= y_{i} <= m, 1 <= p_{i} <= 10^{6}. A triplet of this form signifies that by the intersection (x_{i}, y_{i}) p_{i} passengers await the bus. Each intersection is described in the input data once at the most. The total number of passengers waiting for the bus does not exceed 1 000 000 000.
OutputYour programme should write to the standard output one line containing a single integer  the greatest number of passengers the bus can take.
ExampleFor the input data: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 2the correct outcome is: 11 Print friendly version 