Пиріжок Дракона
Пиріжок Дракона — це головоломка зі ковзанням на торі. Поверхня тора розділена на дев'ять квадратів, як показано на Рисунку 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 означає, що квадрат порожній.
Останній рядок містить два нулі і не обробляється.
Вихідні дані
Для кожного тесту вивести в окремому рядку найменшу вартість, за яку можна отримати кінцевий стан. Загальна вартість дорівнює сумі вартостей ходів усіх фішок з початкового стану в кінцевий.