Вартість маршруту#4444
На кожній клітинці шахової дошки розміром 8 \times 8 записано ціле невід'ємне число. Король може переміщуватись по шаховій дошці з лівого нижнього кута у правий верхній, переміщуючись лише праворуч, вгору, або праворуч-вгору. При цьому вартість проходу через дану клітинку дорівнює числу, записаному на цій клітинці.
Перемістіть короля з лівого нижнього кута у правий верхній з найменшою вартістю проходу.
На вхід програмі подається вісім рядків, кожен рядок містить вісім цілих невід'ємних чисел, які не перевищують . У лівому нижньому куті завжди записано число .
У першому рядку виведіть єдине число - мінімальну вартість проходу з лівого нижнього кута у правий верхній. У другому рядку виведіть маршрут короля заданої вартості, відокремлюючи клітинки одним пропуском. Маршрут повинен починатись клітинкою a1 і завершуватись клітинкою h8.
Приклад 1