Warp Speed II

Time Limit: 16000ms

Memory Limit: 65535kb


In the not-so-distance future, space engineers can inventa new technology for traveling through space and name it as “warp-drive”. Thiswarp-drive can make a spaceship travel faster than light speed. It works bybending an amount of distance in space and make a ship travel through that bendedspace in a single “hop”. To travel through space, a spaceship (that is equippedwith this warp-drive) may have to perform more than one hop between thebeginning and the endingpoints. The amount of energy/power to hop depends on the currentstate/configuration of the warp-drive. And some amount of energy is alsoconsumed in order to prepare or switch to any warp-drive state.


Suppose that you are an engineer on a battle spaceship.Your duty is to control/configure the warp-drive so that it will consume asless energy as possible for any traveling. For each traveling, you will beprovided with a sequence of hops, which you have to find a corresponding sequenceof warp-drive configurations that use the lowest energy.

In order to accomplish your duty, you have to build acomputer program to find the lowest energy of warp-drive configuration sequencefor any given hop sequence based on two tables of warp-driver energyconsumptions. The first table shows the energy for switching between any twostates. The second table shows the energy consumption related to warp-drive statesand hops.


Input is a standard input which consists of 4 parts, separated by a blankline.

The first part defines the sizes of warp-drive states and hop types.

l  It contains ofonly one line. This line contains 2 numbers separated by a space. These 2 numberare

o Size of warp-drivestates(N), which is between 1 and 100.

²  The state id isstarting from 0 to N-1.

²  The first state(id #0) is the idle state. At this and only this state, the warp-drive can'tperform any hop. (It is the default starting and ending state for any outputstate sequence.)

o Size of differenttypes of hops(H), which is between 1 and 1,000.

²  The hop id from 0 to H-1.

The second part is a table showing the energy for switching warp-drivestates. The table size is N rows and N columns, which contains N2 energy values.

l  There are N lines.Each line contains N energy values. These values are between 1 and 100.

l  Each energy valuecan be indexed by its row and column. The row and column indexes are the stateids of the current and next warp-drive states respectively. Please be notifiedthat these two indexes are starting from 0.

²  For example, thevalue at (row index, column index) = (5,0) is the energy for witchingwarp-drive state from number 5 to 0. (This value is the first number in the sixthline.)

The third part is a table showing the energy consumption in performinghops for each state drive.ACM-ICPC Asia Hatyai Regional Programming Contest –November 16, 2012 – PSU, Hatyai 13

The table size is N rows and H columns, which contains N by H values.

l  There are N lines. Each line contains H energy values.These values are between 1 and 100.

l  Each energy valuecan be indexed by its row and its column. The row index is the id of thecurrent warp-drive state. The column index is the id of the hop. Please benotified that these two indexes are starting from 0.

o For example, thevalue at (row index, column index) = (1,9) is the energy for warp-driveat state #1 to perform hop #9 . (This value is the tenth number in the secondline.)

o Please be notifiedthat in the very first line of this part, which corresponds to the state #0 orthe idle state, all numbers are zeros. This rather means that it can't performany hop in this state.

The fourth part is a set of hop sequences. The number of sequences in thisset is between 1 and 1,000.

l  The number oflines is 1 up to 1,000.

l  Each line in thispart contains one hop sequences.

l  The number of hopsin a sequence is between 1 and 1,000.

l  Each hop is anumber (starting from 0 to H-1) and is separated with space.

The blank line after the fourth part is the termination of the input.


For each hop sequence in the fourth part of the input, write 2 parts ofoutput as follows

l  In the first line,write the total amount of energy which must be minimum.

l  In the followingline, write the solution. The solution contains a sequence of warp-drive statescorresponds to the given hop sequence. (The size of input and output sequence mustbe equal.) If there are two or more possible solutions which consumes the same amountof energy, write only the sequence which contains the lowest states comparing fromleft to right.

Sample Input

4 5
1 2 6 1
3 4 3 17
2 3 9 3
1 21 1 8
0 0 0 0 0
3 3 2 4 3
2 2 4 3 1
4 2 2 7 7
0 4
1 2 3 2

Sample Output

3 2
1 1 2 3


There are 15 lines in the sample input and 4 lines in the sample output.

In the first sample output (solution for input line #13), the minimum total energy is 9. The warp-drive state sequence is [3 2] or [0- 3 2 -0]. There are 3 state switchings from 0 → 3, 3 → 2, and 2 → 0, which consumes 1 + 1 + 2 = 4. And two hops (0 and 4) at state 3 and 2 respectively, which consumes 4 +1 = 5. So the total energy is 4 + 5 = 9.

In the last sample output, the minimum energy is 23. The solution is [0- 1 1 2 3 -0] which draws 23 energy in total.