Problem Description

Old C is a programmer.

As a lazy programmer, Old C often spends his time playing block games on his computer. The game is confined to a grid of $R$ rows and $C$ columns, where each cell can be adjacent to another if they share a common edge. Some of these common edges are special and are arranged in a strong pattern. The first edge between the first two cells in the first row is special. Then, the special edges repeat every 4 cells horizontally and every 2 cells vertically. All odd-numbered columns have special edges with the next column, and the rows where these edges appear alternate between odd and even numbers from left to right.

The diagram below shows a grid of $R=C=8$, with blue edges indicating the special edges. Starting from the first row, the edge between the first and second columns is special. Due to the vertical periodicity of 2, all odd-numbered rows have special edges between the first and second columns. Due to the horizontal periodicity of 4, all odd-numbered rows also have special edges between the fifth and sixth columns, and so on if the grid is larger. Since all odd-numbered columns have special edges with the next column, the edges between the third and fourth columns, and the seventh and eighth columns are also special, appearing on even-numbered rows. If the grid is larger, we can identify all special edges using the same method.

Each cell in the grid can hold one block. At the start of the game, some cells are already occupied by blocks, while others are not. Old C dislikes certain patterns of blocks, especially if they form a shape that he dislikes (with the special edges in the specified positions), even if the pattern can be formed after any number of rotations or flips.

To prevent giving up, Old C decides to remove some blocks from the grid before he loses motivation. However, removing each block costs a certain number of coins, and the costs vary. Old C wants to minimize his coin expenditure but needs to ensure that no disliked patterns can be formed. Old C is too lazy to think, so he asks you to solve this problem for him.

Input Format

The first line contains three positive integers $C, R, n$, indicating the grid has $C$ columns and $R$ rows, with $n$ cells containing blocks.

The next $n$ lines each contain three positive integers $x, y, w$, indicating that the cell at the $x$-th column and $y$-th row contains a block, and removing it costs $w$ coins. It is guaranteed that no cell is repeated and all cells are within the grid's bounds.

Output Format

Output a single integer, the minimum number of coins required.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample 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 

Sample Output #2

15

Notes/Hints

For the first two test points, $1 \leq C, R \leq 100$, $1 \leq n \leq 20$.

For the third to sixth test points, $1 \leq C, R \leq 10^5$, $2000 \leq n \leq 5000$, with varying data.

For the seventh to tenth test points, $1 \leq C, R \leq 10^5$, $30000 \leq n \leq 10^5$, with varying data.

For all test points, $1 \leq C, R, n \leq 10^5$, $1 \leq w \leq 10^4$.

见题面 Input 部分

见题面 Output 部分