10086 - Test the Rods

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

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

Input

輸入有多組測資，每組第一行會有兩個整數 T₁, T₂ (1 <= T₁ + T₂ <= 300)，表示內容如上描述，接下來會有一行一個整數 n (1 <= n <= 30)，接下來會有 n 組地點資訊。

對於地點，會有一個整數 m_i (1 <= m_i <= 20)，表示該地點有多少樣品要被檢測。

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

當 T₁ = T₂ = 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