Warp Speed II

In the not-so-distant future, space engineers invent a new technology for traveling through space and call it the warp-drive. A warp-drive lets a spaceship travel faster than light by bending a stretch of space and letting the ship cross it in a single hop. To get from one point to another, a ship equipped with a warp-drive may need to perform several hops in a row.

The energy needed for one hop depends on the current state (configuration) of the warp-drive, and switching the warp-drive from one state to another also costs energy.

You are an engineer on a battle spaceship, and your job is to configure the warp-drive so that each trip consumes as little energy as possible. For every trip you are given a sequence of hops, and you must choose one state per hop so that the total energy is minimized.

You are given two energy tables. The first gives the energy to switch between any two states; the second gives the energy to perform each hop in each state. For every hop sequence, report the minimum total energy and the corresponding state sequence.

The input is given on standard input and consists of four parts separated by blank lines.

Part 1 — sizes. One line with two integers separated by a space.

• $N$ ($1 \le N \le 100$): the number of warp-drive states, with ids $0$ to $N-1$. State $0$ is the idle state: only in this state can the warp-drive perform no hop, and it is the default start and end state of every state sequence.
• $H$ ($1 \le H \le 1000$): the number of hop types, with ids $0$ to $H-1$.

Part 2 — state-switch table. $N$ lines, each with $N$ integers between $1$ and $100$. The value in row $i$, column $j$ is the energy to switch the warp-drive from state $i$ to state $j$ (rows and columns are indexed from $0$).

Part 3 — hop-energy table. $N$ lines, each with $H$ integers between $1$ and $100$. The value in row $s$, column $c$ is the energy to perform hop $c$ while in state $s$ (indexed from $0$). The first line (state $0$, idle) is all zeros, because the idle state cannot perform any hop.

Part 4 — hop sequences. Between $1$ and $1000$ lines, each a single hop sequence. A sequence contains between $1$ and $1000$ hops, each a hop id from $0$ to $H-1$, separated by spaces.

For each hop sequence in Part 4, print two lines:

• the minimum possible total energy;
• the chosen state sequence, one state per hop (so it has the same length as the hop sequence), with states separated by spaces.

The total energy of a trip is the energy to switch from idle state $0$ into the first chosen state, plus the hop energy at each chosen state, plus the switch energy between consecutive chosen states, plus the energy to switch from the last chosen state back to idle state $0$.

If several state sequences achieve the same minimum energy, print the one that is smallest when the state ids are compared from left to right (the lexicographically smallest).

Consider the hop sequence 0 4 from the first example. The optimal state sequence is 3 2 with total energy $9$: the switches $0 \to 3$, $3 \to 2$, $2 \to 0$ cost $1 + 1 + 2 = 4$, and performing hop $0$ in state $3$ and hop $4$ in state $2$ costs $4 + 1 = 5$, for $4 + 5 = 9$ in total.

For the hop sequence 1 2 3 2, the optimal state sequence is 1 1 2 3 with total energy $23$.