2013年7月23日 星期二

10086 - Test the Rods

National Construction and Project Centre (NCPC) 和 Bureau of Civil Engineering Works (BCEW) 是國內最具權威的測試與驗證道路的機構。

有一家名為 Get and Do 的建設公司得到在不同地點的建設專案,在這個 n 個地點的道路中,想要請 NCPC 檢測 T1 個道路、BCEW 檢測 T2 個道路,在每一個地點有不同個數的道路需要被檢測,保證所有檢測的樣本總數等於 T1 + T2 ,假設第 i (1 <= i <= n)地點中,有 mi 個樣本需要被檢測,而在該地點時,對於 NCPC、BCEW 的檢測費用是看檢測的個數,如果要在此檢查 j 個樣本,對於 NCPC 花費 Ci,j,1、BCEW 花費 Ci,j,2 ,找到一種分配方式,具有最少花費。


Input
輸入有多組測資,每組第一行會有兩個整數 T1, T2 (1 <= T1 + T2 <= 300),表示內容如上描述,接下來會有一行一個整數 n (1 <= n <= 30),接下來會有 n 組地點資訊。
對於地點,會有一個整數 mi (1 <= mi <= 20),表示該地點有多少樣品要被檢測。

而接下來會有 mi 個整數 Ci,j,1 (1 <= j <= mi),接續也會有 mi 個整數
Ci,j,2 (1 <= j <= mi),分別表示 NCPC、BCEW 在該地點檢測樣本個數的花費。



T1 = T2 = 0 ,結束程式。

Output
對於每組測資輸出兩行,第一行有一個整數表示最少花費測試所有的道路。
第二行輸出,輸出 n 個整數,第 i 個整數表示 NCPC 在第 i 地點的檢測個數,這裡可以暗示出 BECW 檢測了多少個。如果有多組分配方式,任何一組都可以。

在每組測資後,輸出一行空行。

Sample Input
10 12
5
5
10 30 70 150 310
10 20 40 60 180
7
30 60 90 120 160 200 240
20 60 100 130 160 200 240
4
40 60 80 100
30 70 100 120
3
60 120 180
20 50 90
3
30 70 100
30 70 100
0 0


Sample Output
580
1 3 4 0 2