Задача 7. Все перекаты да перекаты

[mka91x]

Задача 7. Все перекаты да перекаты
Имя входного файла: standard input
Имя выходного файла: standard output
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 MiB

Рассмотрим игральный кубик, стоящий на бесконечном поле, на гранях которого написаны некоторые целые положительные числа, возможно, повторяющиеся. Будем перемещать
этот кубик по полю, перекатывая через ребра в его основании, при этом не будем возвращаться на тот участок поля, где кубик стоял ранее. В ходе перемещений будем суммировать
значения, попадающие на верхнюю грань кубика. Определите, какую минимальную сумму мы можем получить в результате. Числа, находящиеся на верхней грани в начальном и
конечном положениях кубика, также участвуют в сумме.

Формат входных данных

В первой и единственной строке 7 целых положительных чисел.
Первые шесть из них – значения на гранях кубика в следующем порядке их перечисления:
верхняя, нижняя, левая, правая, передняя, задняя. Каждое из значений не превышает 1 000.
Последнее, седьмое число K – количество перекатываний кубика, 1 ⩽ K < 18.

Формат выходных данных

В первой и единственной строке одно целое неотрицательное число – минимальная сумма
значений, попавших на верхнюю грань кубика в процессе перекатываний, включая исходное
и конечное.