301 - Transportation

鐵路運輸公司TransRuratania經營一項由城市A到城市B的鐵路運輸事業，沿途有許多停靠站，各停靠站由A到B依序編號，以A為編號0，B為編號 m。該公司進行一項研究用來改善旅客的載運量，進而提高收益。火車最多可同時搭載 n 位旅客。火車票價等於旅客上車後沿途停靠站的個數(包含目地的)，火車由A城出發，並可於各站訂票，由車站S訂的票表示會由S開始劃位直到目的地為止。由於火車承載量的限制，該鐵路公司可能無法接受所有的訂位需求，訂票的原則為必須全部接受訂位的數量或是全部拒絕該數量。
 

給定由A到B各站所有的訂位需求，本題請你寫一個程式計算該公司最大可能的收益，單一訂票的收益等於人數乘於票價，總收益等於所有訂票收益的總和。

Input

每組測試資料的第一列有三個整數 n、m及訂票的數目，接下來的每一列為其訂票資訊，每筆資料有三個整數：出發站、目地站及旅客人數，最多會有22筆訂票資訊，且 m 值最大為7。當 n、m 及訂票數目皆為零時表示測試資料結束。

Output

請輸出每組測試資料的最大收益。

Sample Input

10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0

Sample Output

19
34

原文出處