2402: 招募士兵

小W拥有一个国家，现在他希望建立一支军队来保护他的国家。他选中了N个女孩和M个男孩希望招募他们成为他的士兵。在没有任何先决条件的情况下，他招募一个士兵需要花费10000RMB。现在小W可以利用这些人之间的关系来减少他的花费。如果女孩X和男孩Y存在有一个关系值D（两人之间可能有多个关系值），而且她们之中有一个人被招募了。那么小W可以在招募另一个人的时候减少D的花费（实际10000-D的费用）。

现在给你这些男孩女孩之间的关系，希望你告诉小W告诉他招募所有人的最少花费。

注意：招募某一个人时，只能利用一个关系。

输入文件conscription.in中文件第一行包含三个整数N，M，R。表示N个女孩，M个男孩与R条关系。

conscription.out中只有一行一个数，为最小费用。

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 

71071