Old C is a programmer. As a lazy programmer, Old C often plays games on his computer to kill time.

The game is played on a grid of $R$ rows and $C$ columns. If two squares share a common edge, they are called adjacent. The common edges between adjacent squares have special properties. These special edges follow a very strong pattern. First, the edge between the first two squares in the first row is special. Then, special edges repeat every 4 squares horizontally, and every 2 squares vertically. All odd-numbered columns and the next column have special edges between them.

The figure below shows an $R = C = 8$ grid, with special edges marked in blue. First, in row 1, there is a special edge between column 1 and column 2. Because the vertical period is 2, all odd rows have special edges between column 1 and column 2. Because the horizontal period is 4, all odd rows also have special edges between column 5 and column 6. If the grid is large enough, all odd rows have special edges between column 9 and column 10, column 13 and column 14, and so on. Because all odd columns and the next column have special edges between them, the edges between column 3 and column 4, column 7 and column 8, etc., are also special. If the grid is larger, we can find all special edges in the same way.

Each square in the grid can hold exactly one block. At the beginning of the game, some squares are already occupied by blocks, while others are empty. Old C hates the shape shown in the figure below. If he finds that some blocks are arranged in this annoying shape (the positions of the special edges are as shown in the figure), he will easily give up, even if he can rearrange them by any number of rotations or flips. Old C also gives up if he finds this annoying shape.

To prevent giving up, Old C decides to remove some blocks from the squares before he gives up, so that the remaining blocks do not form the annoying shape. However, removing a block in the game costs some gold coins, and each block requires a different amount of gold coins to remove. Old C naturally wants to spend as little gold as possible, but what is the minimum cost? Old C is deep in thought, so he has handed this problem to you.

Input

The input contains three integers $C, R, n$, representing a grid with $C$ columns and $R$ rows, where $n$ squares are occupied by blocks.

Next, $n$ lines each contain three integers $x, y, w$, indicating that there is a block in the square at column $x$ and row $y$, and removing it costs $w$ gold coins. It is guaranteed that there are no duplicate positions and all positions are within the grid boundaries.

Output

Output a single integer representing the minimum cost in gold coins.

Examples

Input 1

2 2 4
1 1 5
1 2 6
2 1 7
2 2 8

Output 1

5

Note 1

As shown in the figure, in a $2 \times 2$ grid, every square has a block. Removing blocks costs gold as marked in the figure. These 4 blocks form the annoying shape Old C hates. By removing the block at column 1, row 1, which costs 5 coins, the remaining blocks cannot form the annoying shape. Clearly, this removal plan is the cheapest.

Input 2

3 3 7
1 1 10
1 2 15
1 3 10
2 1 10
2 2 10
2 3 10
3 1 10

Output 2

15

Note 2

As shown in the figure. It is easy to see that if we do not remove the blocks in row 2 of column 1, we must remove at least two blocks to ensure the annoying shape does not exist, costing at least 20 gold coins; but if we remove the blocks in row 2 of column 1, the original annoying shape no longer exists, and it only costs 15 gold coins.

Constraints

For test cases 1–2: $1 \le C, R \le 100, 1 \le n \le 20$; For test cases 3–6: $1 \le C, R \le 10^5, 2000 \le n \le 5000$; For test cases 7–10: $1 \le C, R \le 10^5, 30000 \le n \le 10^5$; For all test cases: $1 \le C, R, n \le 10^5, 1 \le w \le 10^4$.