|
執行檔 |
income.exe |
輸入檔 |
income.in |
|
執行時間限制 |
30秒 |
輸出檔 |
income.out |
為了挽救日漸虧損的營運，台汽決定在花東開發一條新的路線。這條新的路線是從台北到墾丁，沿途依序編號著許多停靠站，其中台北編號為0、墾丁編號為m。
台汽打算做用一個全新的模式來改善載客量，以增加他們的收入。由於這個路線上每一車次的載客量為n名乘客，而每張車票的票價為起點和終點站之間所經過的車站數目（包括終點站）。每一列車的每一趟車次從台北出發之前，沿途的每一個車站都會確定好所有的車票訂單。如果有一份車票訂單(假設要x張車票)的起始點是S站，終點是T站的話，表示要保留恰好x張從S站到T站的車票。如果因為載客的限制，而無法接受所有的訂單的話。該公司的政策是：對於某一份訂單，採全部接受或是全部拒絕的態度。
請寫一個程式，對於每一個車次的所有訂單，找出台汽能得到最大收入的組合。對於每一張訂單來說，他們的收入是該訂單的所有乘客數乘上票價。所以，對某一車次來說，總收入即是所有接受訂單的收入總和。
輸入檔案裡面有多組測試資料。在每一組裡面的第一行包括了三個整數：列車的載客量n，墾丁站的編號m，以及車票訂單的總數p。以下的p行包含車票訂單。每張車票訂單包括三個整數：起點站、終點站、還有乘客數目。在一組測試資料中，最多會有22張車票訂單。m最大是7。當某一組測試資料的第一行為三個0時，表示測試檔的結尾。
對每一組對應的測試資料，印出最大可能的總收入，一組一行。
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
19
34