最小染色

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

在这个网格上,有 $N$ 个编号为 $1$ 到 $N$ 的白色棋子。棋子 $i$ 位于 $(A_i, B_i)$。

支付代价 $C_i$ 可以把棋子 $i$ 变成黑色棋子。

求使每一行和每一列都至少有一个黑色棋子的最小总代价。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$ $N$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_N$ $B_N$ $C_N$

输出格式

输出答案。

样例

2 3 6
1 1 1
1 2 10
1 3 100
2 1 1000
2 2 10000
2 3 100000

1110

支付代价 $1110$,把棋子 $2, 3, 4$ 变成黑色棋子,就可以使每一行和每一列都有黑色棋子。

1 7 7
1 2 200000000
1 7 700000000
1 4 400000000
1 3 300000000
1 6 600000000
1 5 500000000
1 1 100000000

2800000000

3 3 8
3 2 1
3 1 2
2 3 1
2 2 100
2 1 100
1 3 2
1 2 100
1 1 100

6

数据范围

• $1 \le H, W \le 10^3$
• $1 \le N \le 10^3$
• $1 \le A_i \le H$
• $1 \le B_i \le W$
• $1 \le C_i \le 10^9$
• 所有数对 $(A_i, B_i)$ 互不相同。
• 每一行和每一列都至少有一个白色棋子。
• 输入中的所有值都是整数。