题目描述

汉诺塔是一个众所周知的数学难题。它由三根杆和许多不同尺寸的圆盘组成，圆盘可以滑到任何杆上。开始时圆盘整齐堆叠，在一根杆上按照尺寸的升序排列，顶部最小，从而形成圆锥形状。

这个难题的目的是将所有圆盘移动到另一个杆，遵守以下简单规则：

• 一次只能移动一个圆盘。
• 每次移动都包括从其中一根杆中取出上层圆盘并将其放在另一根杆的顶部，即只有原盘是杆子最上面的圆盘时才能移动圆盘。
• 大的圆盘不能放在较小的圆盘上面。
• 如果有三个圆盘，可以通过七个动作解决。解决汉诺塔拼图所需的最小移动次数为 $2^n-1$，其中 $n$ 是圆盘的数量。

新版汉诺塔与汉诺塔难题非常相似。在汉诺塔问题中，您需要以最少的移动次数来解决难题，在新版汉诺塔中， 每次移动都需要花费一些钱，而且您需要以 最低的成本 解决相同的难题。在新版汉诺塔开始时，所有 $n$ 个磁盘都在第一个杆上。从杆 $i$ 移动圆盘到杆 $j$（$1≤i,j≤3$）收费 $t_{ij}$ 的钱。新版汉诺塔的目标是将所有圆盘移动到第三个杆。

在这个问题中，给出矩阵 $T$ 和整数 $n$ 表示 $n$ 个圆盘。你需要计算解决新版汉诺塔的最低成本。

输入格式

输入的前三行前三列表示矩阵 $T$，第 $i$ 行第 $j$ 个数为 $t_{ij}(1 ≤ t_{ij} ≤ 10000, i \neq j)$。 最后一行包含一个整数 $n(1≤n≤40)$ 表示圆盘的数量。 保证对所有的 $i$，$t_{ii} =0$。

输出格式

输出为一行，表示解决新版汉诺塔问题的最低成本。

样例

输入#1

0 1 1
1 0 1
1 1 0
3

输出#1

7

输入#2

0 2 2
1 0 100
1 2 0
3

输出#2

19

输入#3

0 2 1
1 0 100
1 2 0
5

输出#3

87