火车票问题

Time Limit: 1000MS

Memory Limit: 65535KB

Description

Fishead的算法可是非常nb的。某天,他被铁道部请去解决一个棘手的问题。
总所周知铁道部一向很坑,买票不易。但是铁道部想赚更多的钱。
现在有一条很长的铁路,从a向b开,途径n个站台(包含ab)。每个站台都有乘客要买票到下游的另一个站台。不同的乘客买不同的站点间的票价格是不同的(有优惠票),但是火车座位就m个,不可能满足所有的乘客,铁道部想要票的总价钱最多(不是满足的乘客最多哦),请输出最多多少钱。

Input

第一行是Case数
对于每个case
第一行是3个整数,n,m,p。2<=n<=50,1<=m<=50,1<=p<=500
接下来p行每行3个数s,t,c,表示某个乘客的起点,终点,和价格。1<=s<t<=n,1<=c<=100

输入case之间有一个空行

Output

返回最多多少钱。

Sample Input

2
5 1 3
1 3 1
3 5 1
2 4 3

5 1 5
1 3 2
3 5 3
1 5 10
1 4 4
4 5 2

Sample Output

3
10

Hint

None

Source

沈宇亮

提交代码