H. Tower Tetris
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tetris is probably the most famous video game in the world. A few months ago an achievement that seemed impossible was achieved, a 13 year old kid nicknamed "BlueScuti" managed to reach the game's kill screen, a moment where the memory of the original game fails and it is assumed that you have reached the "end". Actually this happens in the NES version of the game which is considered the most realistic version of Tetris, current computers can easily beat the game.

You are going to play a similar game, you have to create a tower of $$$2\times1$$$ blocks very similar to those of Tetris, which will be placed in the typical grid of the game. As in Tetris, they will fall from above and will land when they come into contact (at their base) with the ground or with another block.

At some squares of the grid there will be coins of different values that will make up the score of the game: if a block is on top of a coin at the end of the game, the player will get a score equal to its value.

The blocks can be placed vertically or horizontally. However, with the exception of the first block, they must always be placed on top of the last one placed, i.e., at least one square of the new block must be on top of a square occupied by the previous block. In other words, they must form a "tower". In addition, the width of the playing area must be delimited, and blocks may not be placed beyond this limit. The game ends when the maximum height of the playing area is exceeded.

Are you able to determine the highest possible score in Tower Tetris?

Input

The input will form a single test case. The first line will contain two values $$$W,H$$$, which will be the width and height of the board respectively.

Subsequently a number $$$N$$$ will appear, the number of coins in the grid. Finally $$$N$$$ lines with three values $$$X_i, Y_i, V_i$$$, the position where the coin will be described by its coordinates $$$(X_i, Y_i)$$$, and its value $$$V_i$$$. The position is computed assuming that the lower left square is $$$(0, 0)$$$ and the values grow upward and to the right.

  • $$$2 \leq W,H \leq 1,000$$$
  • $$$0 \leq N \leq W\cdot H$$$
  • $$$0\leq V_i \leq 100$$$
  • $$$0 \leq X_i \lt W$$$
  • $$$0 \leq Y_i \lt H$$$
  • Two coins will never be at the same square.
Output

For each case a single $$$D$$$ value must be printed, the maximum number of points that can be obtained in the game, until the upper limit of the playing area is reached.

Examples
Input
5 6
6
2 0 5
1 1 5
0 2 5
0 3 5
0 4 5
2 5 5
Output
30
Input
5 6
6
0 0 5
0 1 5
0 2 30
0 3 5
0 4 5
4 2 60
Output
60
Note