汉诺塔

汉诺塔中有三个柱子编号分别是1,2,3。在一号柱子上有n个圆盘，从顶部到底部依次从小到大，每次可以把柱子上最上面的一个圆盘移动到另外两个柱子的最上面,移动的过程中必须保证放在上面的盘子比放在下面的盘子小，最终要把所有的圆盘都移动到第三根柱子上，且从顶到底也是依次从小到大。已知把一个圆盘从柱子i移动到柱子j的花费是cost[i][j]。求最小花费。

输入包括多组数据 每组数据先输入一个3*3的矩阵，表示cost。(每个数大于0小于等于10000) 然后输入一个n表示圆盘的数量。(n<=40)

对于每个输入数据，输出一个整数表示答案。