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