Laiko ribojimas: 0.5s

Atminties ribojimas: 32MB

Duomenų failas: hanoj4.in

Rezultatų failas: hanoj4.out

Jei norite pateikti savo sprendimą - prisijunkite.

Hanojaus bokštai 4

Vėl žaisime su Hanojaus bokštais (http://en.wikipedia.org/wiki/Tower_of_Hanoi). Viso turėsime tris stiebus, ant pirmojo bus užmauta 1\\leqn\\leq40 žiedų. Reikės rasti minimalią kainą, kurią teks sumokėti perkeliant visus žiedus nuo pirmojo stiebo ant trečiojo.

Įvestis

Pirmojoje eilutėje bus pateiktas skaičius n. Sekančiose eilutėse bus pateikta 3x3 dydžio kainų matrica C. Šios matricos narys 1\\leqC[i][j]\\leq10000 nurodo kainą, kurią reikia sumokėti perkeliant žiedus iš i'tojo stiebo į j'tąjį stiebą (taipogi C[i][i]=0).

Išvestis

Pirmojoje ir vienintelėje eilutėje reikės išvesti žiedų perkėlimo kainą.

Pavyzdys

Pradiniai duomenys Rezultatai 
3
0 2 2
1 0 100
1 2 0
 
19