Problem Statement

We have a grid with $H$ rows and $W$ columns. Let $(i,j)$ denote the square at the $i$-th row from the top and $j$-th column from the left.

On this grid, there are $N$ white pieces numbered $1$ to $N$. Piece $i$ is on $(A_i,B_i)$.

You can pay the cost of $C_i$ to change Piece $i$ to a black piece.

Find the minimum total cost needed to have at least one black piece in every row and every column.

Constraints

• $1 \leq H,W \leq 10^3$
• $1 \leq N \leq 10^3$
• $1 \leq A_i \leq H$
• $1 \leq B_i \leq W$
• $1 \leq C_i \leq 10^9$
• All pairs $(A_i,B_i)$ are distinct.
• There is at least one white piece in every row and every column.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W N
A_1 B_1 C_1
\hspace{23pt} \vdots
A_N B_N C_N

Output

Print the answer.