B. Ханойская башня
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Ханойская башня — это известная математическая головоломка. Она состоит из трех стержней и нескольких дисков различных размеров, каждый диск можно нанизывать на любой стержень. В начале диски аккуратно нанизаны на один из стержней по возрастанию размера, самый маленький диск сверху, таким образом образуя форму конуса.

Цель головоломки — перенести всю стопку дисков на другой стержень, соблюдая следующие простые правила:

  1. За один ход можно переместить только один диск.
  2. Каждый ход заключается в том, что мы берем верхний диск с одного стержня и помещаем его сверху на другой стержень. То есть диск можно перемещать, только если он верхний в стопке.
  3. Никакой диск нельзя класть на диск меньшего размера.

С тремя дисками головоломка решается в семь ходов. Наименьшее количество ходов, необходимое для решения головоломки про Ханойскую башню равняется 2n - 1, где n — количество дисков. (c) перевод английской статьи из Wikipedia.

Головоломка SmallR очень похожа на Ханойскую башню. В Ханойской башне вам требуется переместить все диски на другой стержень за минимальное количество ходов. В головоломке SmallR каждый ход стоит некоторое количество денег, и вам надо решить ту же самую головоломку за минимальную стоимость. При этом в начале все n дисков находятся на первом стержне. Перемещение диска со стержня i на стержень j (1 ≤ i, j ≤ 3) стоит tij единиц денег. Цель головоломки в том, чтобы переместить все диски на третий стержень.

В этой задаче вам дана матрица t и целое число n. Надо посчитать наименьшую стоимость решения головоломки SmallR с n дисками.

Входные данные

Каждая из первых трех строк содержит три целых числа — матрицу t: j-ое число в i-ой строке tij (1 ≤ tij ≤ 10000; i ≠ j). В следующей строке записано единственное целое число n (1 ≤ n ≤ 40) — количество дисков.

Гарантируется, что для всех i (1 ≤ i ≤ 3), tii = 0.

Выходные данные

Выведите единственное целое число — минимальную стоимость решения головоломки SmallR.

Примеры
Входные данные
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