UVA1173 The Finest Chef

# UVA1173 最好的厨师 世界厨师大赛要开始了，一共有来自世界各地的 $n$ 名厨师来参赛，他们的编号为 $0$ 到 $n-1$，但由于资金原因，供他们使用的 $s$ 种设备每种只有一台，每台机器的编号分别为 $0$ 到 $s-1$，每个厨师只需要使用他们可以使用的设备中的其中一台即可，且每台设备只能被一个厨师使用，也就是说编号为 $i$ 的厨师可以花费 $t_{i,j}$ 个单位时间使用编号为 $j$ 的设备，为了尽可能的节省时间，请你求出最短需要花费的总时间是多少？

第一行，一个正整数 $T$，表示测试数据组数 在每组数据中： 第一行两个数 $n,s$ ，分别表示人数与设备台数 $(n \leqslant s \leqslant 250)$ 第二行一个数 $q$ ，表示厨师们使用设备的方案数 $(q \leqslant 350)$ 接下来 $q$ 行，每行三个数 $i,j,t_{i,j}$ ，分别表示厨师编号，可使用设备编号，使用这台设备所花费的时间

共 $T$ 行，每行一个数 $ans$ ，表示合理安排后所花费的最短总时间 ## 样例#1 ### 样例输入#1 ``` 2 4 5 9 0 2 5 0 3 3 1 1 20 1 4 10 2 1 25 2 4 30 3 0 2 3 2 10 3 3 12 3 3 9 0 0 3 0 1 2 0 2 1 1 0 1 1 1 7 1 2 9 2 0 3 2 1 7 2 2 5 ``` ### 样例输出#1 ``` 40 8 ```

对于 100% 的数据，保证 $1 \leqslant n \leqslant s \leqslant 250 , 1 \leqslant q \leqslant 350$