Проблемы, которые требуют поиска минимального пути через некоторую область появляются в различных областях информатики. Например, одним из ограничений в проблеме маршрутизации СБИС является минимизация длины провода. Задача Коммивояжера (ЗК) - поиск маршрута продавца по всех городах с возможностью посетить каждый из них только один раз во время пути - один из канонических примеров \textbf{NP}-полной задачи, для решение которой, по всей видимости, потребуется много времени. В этой задаче рассматривается нахождение минимального пути через сеть пунктов с перемещением во время путешествия только слева направо. Для заданной матрицы чисел \textbf{m}×\textbf{n }вы должны написать программу, которая вычисляет путь минимального веса. Путь начинается где-нибудь в колонке \textbf{1} (первая колонка) и состоит из последовательности шагов, заканчивающийся в колонке \textbf{n }(последняя колонка). Шаг состоит в перемещении из колонки \textbf{i }в соседнюю (по горизонтали или диагонали) колонку \textbf{i+1 }подряд. Первая и последняя строки (строки \textbf{1} и \textbf{m} ) матрицы считаются смежными, т. е. матрица "свёрнута" так, что она представляет собой горизонтальный цилиндр. Допустимые шаги показаны ниже. \includegraphics{https://static.e-olymp.com/content/a4/a49ec87fe2153d1db7b467d154dc51b464c8a0eb.jpg} \textit{Весом} пути является сумма чисел в каждой из посещённых \textbf{n} клеток матрицы. Например, два немного отличающихся пути наименьшего веса в матрицах \textbf{5}×\textbf{6} показано ниже (разница только в цифрах в нижнем ряду). \includegraphics{https://static.e-olymp.com/content/ed/edd52b9d44deca9ef5f8583380e4f435153daa67.jpg} Минимальный путь показан для каждой матрицы. Обратите внимание, что путь в матрице справа использует свойство смежности первой и последней строки. \InputFile Входные данные состоят из последовательности матрицы спецификаций. Каждая матрица спецификации состоит из строк и столбцов размером \textbf{m}×\textbf{n} - именно в таком порядке по строкам следуют \textbf{m}×\textbf{n} целых чисел, где \textbf{m} - это количество строк и \textbf{n} - это количество столбцов. Числа появляются в строках ввода построчно, то есть, первые \textbf{n }целых чисел составляют первую строку матрицы, вторые \textbf{n }целых чисел составляют вторую строку и так далее. Числа в строке будут отделены друг от друга одним или несколькими пробелами. \textit{\textbf{Примечание:}} не гарантируется, что все числа положительные. Вам будет предложено одну или несколько матриц во входном файле. Входные данные завершаются концом файла. Для каждой спецификации количество строк будет между \textbf{1} и \textbf{9} включительно, количество столбцов будет между \textbf{1 }и \textbf{100 }включительно. Вес пути не будет превышать целое число, представимое переменной с помощью \textbf{30} бит. \OutputFile Две строки должны быть выведены для каждой матрицы спецификации из входного файла, первая строка представляет собой путь минимального веса, а вторая строка является стоимостью минимального пути. Путь состоит из последовательности \textbf{n} целых чисел (разделенных одним пробелом), представляющих строки, которые представляют собой минимальный путь. Если есть больше чем один путь минимального веса, необходимо вывести тот, который является лексикографически наименьшим.