ByteCommunicationInc.(BYTECOM)isestablishingitscellularnetworkinByteland. Fromthefirst month of their establishment they are expanding their network very aggressively. Every month they are constructing some transmission tower. They are considering the following policy while establishing their networks.
2/3 Every month BYTECOM will construct a number of cellular towers. But they have constraints for each the numbers of towers in each of the line type. • Every month they can construct unlimited number of towers in each of the TYPE1 lines. • Every month they can construct at most 2 towers in each of the TYPE2 lines. • Every month they can construct at most 3 towers in each of the TYPE3 lines. 4. Initially the construction cost of a tower in cell i is Ci units of money. But because of inflation it will increase by 1 unit of money every month. For example if C5 is 10 then construction of a tower in cell 5 is 10 units of money in first month, 11 units of money in second month, 12 units of money in third months and so on. 5. On month i BYTECOM will construct Mi number of towers with following the policy above. Their plan is to minimize the cost of construction of these Mi towers. In each month they just want to minimize the cost of that month, they dont care for the following months. Now given information of the cells and the monthly plans, help BYTECOM to minimize the cost of tower construction for each of the months. Input Input contains multiple numbers of test cases. First line contains T (1 ≤ T ≤ 10) the number of test cases. Eachtestcaseconsistsof3lines. Firstlinecontainsn(2≤n≤20)andm(1≤m≤10). nisthe number of levels in cellular grid and m is the number of months for which BYTECOM is constructing cellular towers. Second line contains 3n2 − 3n + 1 integers (the total number of cells) .The i-th integer is Ci (1 ≤ Ci ≤ 1000) denoting the cost of construction of a tower in cell i at first month. Third line contains m integers. The i-th integer is Mi (1 ≤ Mi ≤ 50) denoting the number of towers that need to be constructed on i-th month. Output For each test case output contains M + 2 lines. First line is ‘Case i:’ where i the number of test case. Each of the next M lines contains the cost for the ith month in the following format. Month i: c unit of money Where c is the minimum construction cost for Mi towers in month i. Also the input guarantee that for every month the set of Mi cells where building Mi towers costs c amount of money will be unique. No other set of unused cells will cost c or less amount of money in that month. An unused cell is the one where no tower has been built yet. Also it will be always possible to build Mi number of towers in i-th month. The last line is blank. See the output for sample input for details. Sample Input 3 22 3437675 61 32 9 9 9 3 3 10 13 6 11 11 5 13 11 7 5 12 4 6 9
3/3 10 8 33 9 10 5 5 10 6 4 4 3 5 5 7 8 10 12 6 9 5 3 10 8 1 Sample Output Case 1: Month 1: 28 unit of money Month 2: 8 unit of money Case 2: Month 1: 67 unit of money Month 2: 85 unit of money Case 3: Month 1: 49 unit of money Month 2: 76 unit of money Month 3: 11 unit of money