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