题目描述

汉诺塔是一种非常著名的游戏。汉诺塔包括三根柱子和一些圆盘。这些圆盘一开始按照从高到低，从小到大的顺序排列，形成圆锥状的“塔”。解题者的目标是将所有的圆盘按照一开始的顺序放到另一根柱子上。但是，移动的时候，你要遵守以下三条规则：

• 每次只能移动一个圆盘。
• 每次移动时只能拿走任意杆上最顶端的圆盘，并将它移动到另一根杆子上。
• 两个相邻的圆盘不能出现上面的圆盘比下面的圆盘要大的情况。

在只有三个圆盘的情况下，这个问题可以用7步简单地解决。一个通用的计算方法是，如果有 $n$ 个圆盘，那么你可以用 $2^n - 1$ 步来解决它。

现在，我们有了新的问题。小Y发明了一种汉诺塔的衍生游戏。玩汉诺塔时，你需要以最少的步数移动完成所有圆盘，但在小Y的游戏中，每一次移动都需要一定的费用，你要根据汉诺塔的规则来解决小Y的游戏，但是你需要花费最少的费用来将所有圆盘按照规定移动到第三个杆上。在开始时，所有的$n$个圆盘都在第一根杆上。将圆盘从杆 $i$ 移动到杆 $j$ 需要花费$t[i,j]$个金钱单位。保证 $1$ <= $i$，$j$ <= $3$ 。我们会给出费用数组 $t$ 以及圆盘数量 $n$ ，你要计算对于这次的数据，最少需要多少费用才能完成小Y的游戏。

输入格式

输入共四行。前三行为费用数组 $t$ ，第 $i$ 行第 $j$ 个数就是 $t[i][j]$ 。关于 $t[i][j]$ 的意思请看题目描述。第四行为一个数字 $n$ ，代表圆盘的个数。

输出格式

输出仅一行，输出完成小Y的游戏最少需要的费用。

翻译员：helpcyg

翻译纯手打，求管理大大换一下翻译，机翻真的漏洞百出。。。