Tower of Hanoi

汉诺塔是一种非常著名的游戏。汉诺塔包括三根柱子和一些圆盘。这些圆盘一开始按照从高到低，从小到大的顺序排列，形成圆锥状的“塔”。解题者的目标是将所有的圆盘按照一开始的顺序放到另一根柱子上。但是，移动的时候，你要遵守以下三条规则： - 每次只能移动一个圆盘。 - 每次移动时只能拿走任意杆上最顶端的圆盘，并将它移动到另一根杆子上。 - 两个相邻的圆盘不能出现上面的圆盘比下面的圆盘要大的情况。 在只有三个圆盘的情况下，这个问题可以用 $7$ 步简单地解决。一个通用的计算方法是，如果有 $n$ 个圆盘，那么你可以用 $2^n - 1 $步来解决它。 现在，我们有了新的问题。小 Y 发明了一种汉诺塔的衍生游戏。玩汉诺塔时，你需要以最少的步数移动完成所有圆盘，但在小 Y 的游戏中，每一次移动都需要一定的费用，你要根据汉诺塔的规则来解决小 Y 的游戏，但是你需要花费最少的费用来将所有圆盘按照规定移动到第三个杆上。在开始时，所有的 $n$ 个圆盘都在第一根杆上。将圆盘从杆 $i$ 移动到杆 $j$ 需要花费 $t[i][j]$ 个金钱单位。保证 $1 \le i, j \le 3$ 。我们会给出费用数组 $t$ 以及圆盘数量 $n$，你要计算对于这次的数据，最少需要多少费用才能完成小 Y 的游戏。 **【输入格式】** 输入共四行。前三行为费用数组 $t$，第 $i$ 行第 $j$ 个数就是 $t[i][j]$。关于 $t[i][j]$ 的意思请看题目描述。第四行为一个数字 $n$，代表圆盘的个数。 **【输出格式】** 输出仅一行，输出完成小 Y 的游戏最少需要的费用。 翻译员：helpcyg

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.

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 $ .

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

0 1 1
1 0 1
1 1 0
3

7

0 2 2
1 0 100
1 2 0
3

19

0 2 1
1 0 100
1 2 0
5

87