← 返回题目列表

Codeforces · 392/B

B. 河内塔

中文机器翻译题面 查看原题

河内塔是一个著名的数学难题。它由三个杆和许多不同尺寸的圆盘组成,这些圆盘可以在任何杆上滑动。拼图开始时,圆盘按照大小升序整齐地堆叠在一根杆上,最小的位于顶部,从而形成圆锥形。

拼图的目标是将整个堆栈移动到另一根杆上,遵循以下简单规则:

1. 一次只能移动一个磁盘。
2. 每次移动都包括从其中一个堆栈中取出上面的圆盘并将其放在另一个堆栈的顶部,即只有当圆盘是堆栈中最上面的圆盘时才能移动它。
3. 较小的磁盘上不能放置任何磁盘。

使用三个圆盘,可以通过七步来解决这个难题。解决汉诺塔谜题所需的最小移动次数为 2n - 1,其中 n 是圆盘的数量。 (c) 维基百科。

SmallY 的谜题与著名的河内塔非常相似。在汉诺塔谜题中,您需要以最少的步数解决谜题,在 SmallY 的谜题中,每一步都需要花费一些钱,并且您需要以最小的成本解决相同的谜题。在 SmallY 谜题开始时,所有 n 个圆盘都在第一根杆上。将圆盘从 i 杆移动到 j 杆(1 ≤ i,j ≤ 3)需要花费 tij 单位的金钱。该谜题的目标是将所有圆盘移动到第三根杆上。

在这个问题中,给定矩阵 t 和整数 n。您需要计算解决 SmallY 难题(由 n 个磁盘组成)的最小成本。

输入

前三行每一行包含三个整数 - 矩阵 t。第 i 行中的第 j 个整数为 tij (1 ≤ tij ≤ 10000; i ≠ j)。以下行包含一个整数 n (1 ≤ n ≤ 40) — 磁盘数量。

保证对于所有 i (1 ≤ i ≤ 3),tii = 0。

输出

打印一个整数——解决 SmallY 难题的最小成本。

示例

输入 #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