Problem1383--院长PIPI

1383: 院长PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 159  Solved: 87
[Submit] [Status] [Web Board] [Creator:]

Description

CSU校医院院长PIPI想组建一支医疗小队支援武汉。小队需要征募n名男医生,以及m名女护士。每征募一个人需要花费10000元劳务费。
但是PIPI发现在这些男医生和女护士之间存在一些亲密关系,通过这层关系就可以少花一些钱。
具体的说,给出若干男女之间的亲密度,征募一个人的费用为10000-(已经征募的人中和自己亲密度的最大值)。
现在要求通过适当的征募顺序使得总费用最少。

Input

第一行给出两个整数n,m,c。c表示关系数。(1<=n,m<=10000,c<=50000)
接下来c行,每行给出两个整数u,v,r,分别表示男医生编号、女护士编号、亲密度。编号从0开始。

Output

输出一个整数,表示答案。

Sample Input

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

Sample Output

71071

Source/Category