Олимпиада по программированию NIX
3-го октября 2004 года
Задачи [A] [B] [C] [D] [E] [F]

Ретрокубик

Time limit = 5 Секунд(ы)

В рамках рекламной кампании "Расширь свою память!", проводимой филиалом компанией "НИКС" в городе N-cк, по устоявшеся всеS-ской традиции, в качестве одной из задач участникам предлагается раритентая задача с командного тура Санкт-Петербурга. На одной из клеток шахматной доски (см. рисунок) стоит кубик. На гранях кубика написаны неотрицательные целые числа, не превосходящие 1000. Кубик можно перемещать на смежную клетку, перекатывая его через соответствующее ребро в основании. При движении считается сумма чисел, попавших в основание кубика (каждое число считается столько раз, сколько раз кубик оказывался на данном основании). Требуется найти такой путь движения кубика от начальной до заданной конечной клетки, при котором сумма чисел будет минимальной. Числа, стоящие в основании кубика в начальной и конечной позициях тоже входят в сумму. Начальная и конечная позиции различаются.
Кубик-экспонат. Руками не трогать.
Жюри олимпиады советует участникам тура, не помнящим наизусть решений всех школьных олимпиад Санкт-Петербурга, решать данную задачу как обычную.

Вход В начале записываются координаты начальной и конечной позиций кубика. Координата состоит из прописной буквы и следующей за ней без пробела цифры (см. пример и рисунок). Далее следуют 6 чисел, записанных на гранях кубика. Первым идет число, записанное на передней грани, далее — на задней, верхней, правой, нижней и левой гранях соответстсвенно. Исходный файл не содержит пустых строк.

Выход Необходимо вывести на отдельной строке минимальную сумму.

Вход#1
a1 b2 1 1 1 1 1 1
Выход#1
3 
Вход#2
e2 e3 0 8 1 2 1 1
Выход#2
5