CF392B.Tower of Hanoi

The Tower of Hanoi is a well-known mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2_n_ - 1, where n is the number of disks. (c) Wikipedia.

SmallY's puzzle is very similar to the famous Tower of Hanoi. In the Tower of Hanoi puzzle you need to solve a puzzle in minimum number of moves, in SmallY's puzzle each move costs some money and you need to solve the same puzzle but for minimal cost. At the beginning of SmallY's puzzle all n disks are on the first rod. Moving a disk from rod i to rod j (1 ≤ i, j ≤ 3) costs t__ij units of money. The goal of the puzzle is to move all the disks to the third rod.

In the problem you are given matrix t and an integer n. You need to count the minimal cost of solving SmallY's puzzle, consisting of n disks.

汉诺塔是一个著名的数学谜题。它由三根柱子和若干个大小互不相同的圆盘组成，这些圆盘可以滑动到任意一根柱子上。初始状态下，所有圆盘按尺寸升序整齐地叠放在其中一根柱子上，最小的圆盘位于顶部，从而形成一个圆锥形。

该谜题的目标是将整叠圆盘移动到另一根柱子上，并遵守以下简单规则：

1. 每次只能移动一个圆盘；
2. 每次移动包括将某根柱子最上方的圆盘取下，并将其放置到另一根柱子的顶部（即：只有当一个圆盘位于某根柱子最顶端时，才可被移动）；
3. 任何圆盘均不可放在比它更小的圆盘之上。

对于三个圆盘的情形，该谜题可在七步内完成。求解含 $n$ 个圆盘的汉诺塔谜题所需的最少移动步数为 $2^n - 1$。（© 维基百科）

SmallY 的谜题与著名的汉诺塔谜题非常相似。在经典汉诺塔谜题中，目标是以最少的移动步数完成谜题；而在 SmallY 的谜题中，每次移动均需花费一定费用，目标则是以最小总费用完成相同的谜题。SmallY 谜题初始时，全部 $n$ 个圆盘均位于第一根柱子上。将一个圆盘从第 $i$ 根柱子移动到第 $j$ 根柱子（其中 $1 \le i, j \le 3$）需花费 $t_{ij}$ 单位金钱。谜题的目标是将所有圆盘全部移动至第三根柱子上。

本题中，你将获得一个矩阵 $t$ 和一个整数 $n$。你需要计算由 $n$ 个圆盘构成的 SmallY 谜题的最小解决成本。

Each of the first three lines contains three integers — matrix t. The j-th integer in the i-th line is t__ij (1 ≤ t__ij ≤ 10000; i ≠ j). The following line contains a single integer n (1 ≤ n ≤ 40) — the number of disks.

It is guaranteed that for all i (1 ≤ i ≤ 3), t__ii = 0.

前三行每行包含三个整数——矩阵 $t$。第 $i$ 行的第 $j$ 个整数为 $t_{ij}$（$1 \leq t_{ij} \leq 10000$；$i \neq j$）。接下来的一行包含一个整数 $n$（$1 \leq n \leq 40$）——圆盘的数量。

保证对所有 $i$（$1 \leq i \leq 3$），均有 $t_{ii} = 0$。

Print a single integer — the minimum cost of solving SmallY's puzzle.

输出一个整数——解决 SmallY 的谜题的最小代价。