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

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

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

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

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

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