Problem B

Test the Rods

Input: standard input

Output: standard output

 

National Construction and Project Centre (NCPC) and the Bureau of Civil Engineering Works (BCEW) have been given the authority of testing and certifying the quality of rods used in construction works in the country. The Get and Do construction company has recently got a contract of construction at different sites of the country. Before the construction can start they want to get the rods from their n sites tested either at NCPC or at BCEW. Get and Do has got the permission of testing T₁ rods at NCPC and T₂ at BCEW. There are m_i samples at site i (1 <= i <= n). Sum total of these samples over all the n sites is just equal to (T₁ + T₂). The cost of testing j items from site i at NCPC is C_i,j,1 and that of testing at BCEW is C_i,j,2. Write a program to find a minimum cost testing schedule for the Get and Do company.

 

Input

The input may contain multiple test cases. The first line of each test case contains the two nonnegative integers T₁ and T₂ (1 <= T₁ + T₂ <= 300). The next line contains n (1 <= n <= 30). Then follow 3n lines. For 1 <= i <= n, line (3i - 2) contains the value of m_i (1 <= m_i <= 20), line (3i - 1) contains m_i nonnegative integers C_i,j,1 (1 <= j <= m_i) and line 3i contains m_i nonnegative integers C_i,j,2 (1 <= j <= m_i). You may assume that 0 <= C_i,j,1, C_i,j,2 <= 1000.

 

A test case containing two zeros for T₁ and T₂ terminates the input, and this case must not be processed.

 

Output

For each test case in the input print two lines. The first line contains an integer giving the minimum cost for testing all the samples at NCPC and BCEW. The next line contains n integers with two consecutive integers separated by a single space. The i-th integer gives the numbers of samples from site i that are tested at NCPC (it is implicit that the rest are tested at BCEW). Note that the second output line is not unique, and hence any optimal testing schedule is acceptable. Print a blank line after the outputs of each test case.

 

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