J12 例题-4 征募

题目描述

$\text{Windy}$ 有一个国家，他想建立一支军队来保护他的国家。他挑选了 $N$ 个女孩和 $M$ 个男孩，想把他们收集起来当他的士兵。要收缴一名没有任何特权的士兵，他必须支付 $1$ 万元人民币。女孩和男孩之间有一些关系，$\text{Windy}$ 可以利用这些关系来降低成本。如果女孩 $x$ 和男孩 $y$ 的关系是 $d$，并且其中一个已经被收取，$\text{Windy}$ 可以用 $10000-d$ 人民币收取另一个。现在考虑到女孩和男孩之间的所有关系，你的任务是找到 $\text{Windy}$ 必须支付的最低金额。请注意，收集一名士兵时只能使用一个关系。

输入格式

输入的第一行是测试用例的数量。

每个测试用例的第一行包含三个整数，$N$、$M$ 和 $R$。

然后是 $R$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $d_i$。

每个测试用例前都有一个空行。

输出格式

对于每个测试用例，在一行中输出答案。

输入样例

2

5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781

5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133

输出样例

71071
54223

样例说明

如上所述。

数据范围

对于$100\%$的数据，保证 $1 \le N, M\le 10000,0\le R\le 50,000,0\le xi<N,0\le yi<M,0<di<10000$；