|
I |
Input: Standard Input Output: Standard Output |
|
Byte Communication Inc. (BYTECOM) is establishing its
cellular network in Byteland. From the
first 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.
1.
BYTECOM have divided the Byteland into a logical hexagonal
grid with N levels. Below is the example of a hexagonal grid with 4 levels.
First level is the center and it
contains only cell 1. The number of cells in subsequent levels is 6,12,18,….. 2nd
level contains cells from 2 to 7, 3rd level contains cells from
8-19, 4th level contains cells from 20-37,… In each of the first the
lowest cell is numbered. Then the rest of the cells are numbered in clockwise
order.
2.
Each transmission tower covers exactly
one cell. So they will not build multiple towers in the same cell.
3.
There are 3 types of lines.
·
The
lines parallel to the connecting lines of the center of cell 1 and cell 2 is
TYPE1 line. For example cell 14 and cell 29 are in the same TYPE1 line. Same
for the cell pairs (4, 28), (32, 35), (23, 25) etc.
·
The
lines parallel to the connecting lines of the center of cell 1 and cell 3 is
TYPE2 line. For example cell 15 and cell 11 are in the same TYPE2 line. Same
for the cell pairs (4, 31), (10, 32), (16, 23) etc.
·
The
lines parallel to the connecting lines of the center of cell 1 and cell 4 is
TYPE3 line. For example cell 13 and cell 17 are in the same TYPE3 line. Same
for the cell pairs (5, 27), (10, 37), (16, 28) etc.
·
To
clarify more there is not any other type of line. For example cell 3 and cell 5
is not in any type of line. Same for the cell pairs (4, 6), (12, 29) etc.
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 don’t 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. Each test case consists of 3 lines. First
line contains n(2≤n≤20) and m(1≤m≤10). n is the 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 i’th 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
Output for Sample Input
|
3 2
2 3
4 3 7 6 7 5 6
1 3
2 9
9 9 3 3 10 13 6 11 11 5 13 11 7 5 12 4 6 9 10
8 3
3 9
10 5 5 10 6 4 4 3 5 5 7 8 10 12 6 9 5 3 10
8 1 |
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 |
Problem setter: Abdullah al
Mahmud, Special Thanks: Rujia Liu, M. M. Rahman