Пирожок Дракона
Пирожок Дракона - это головоломка со скольжением на торе. Поверхность тора разбита на девять квадратов как показано на Рисунке 1. Два квадрата с общей стороной обозначены одной буквой. На Рисунке 2 отображены пары квадратов, являющиеся соседними. Фишки пронумерованы числами от 1 до 8 и размещены на восьми из девяти квадратах, последний квадрат остается пустым.
Рисунок 1. 3×3 Тор Пирожка Дракона
Фишка может перемещаться (скользить) в пустую ячейку из одной из соседних ячеек. Задача головоломки - путем перемещений фишек получить из начальной комбинации заданную. На Рисунке 3 приведен пример перемещений фишек из одного состояния в результате четырех возможных ходов. Стоимость перемещения фишки зависит от направления, но не от ее местоположения.
Ваша задача - найти наименьшую стоимость перемещения фишек из начального состояния в конечное.
Рисунок 2. Соседы
Рисунок 3. Примеры операций скольжения
В отличии от задачи на плоскости, на торе любое конечное состояние фишек может быть получено из любого начального состояния.
Входные данные
Состоит из не более чем 30 тестов.
Каждый тест состоит из семи строк. Первая строка содержит два натуральных числа c_h и c_v - стоимость передвижения фишки в горизонтальном и вертикальном направлении. Оба значения c_h и c_v меньше 100. Следующие три строки задают начальное расположение, а последние три строки - финальное в следующем формате:
d_A d_B d_C
d_D d_E d_F
d_G d_H d_I
Каждая строка содержит три цифры, разделенных пробелом. Цифра d_X (X одна из букв от A до I) указывает на состояние квадрата X как показано на Рисунке 2. Цифры 1, ..., 8 указывают на номер фишки в квадрате. Цифра 0 означает, что квадрат пустой.
Последняя строка содержит два нуля и не обрабатывается.
Выходные данные
Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую можно получить конечное состояние. Общая стоимость равна сумме стоимостей ходов всех фишек из начального состояния в конечное.