Проблеми, які вимагають пошуку мінімального шляху через деяку область з'являються у різних областях інформатики. Наприклад, одним з обмежень у проблемі маршрутизації НВІС є мінімізація довжини провідника. Задача Комівояжера (ЗК) - пошук маршруту продавця по усіх містах з можливістю відвідати кожне з них лише один раз на своєму шляху - один з канонічних прикладів \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} цілих чисел (відокремлених одним пропуском), що подають рядки, які є мінімальними шляхами. Якщо є більше ніж один шлях мінімальної ваги, необхідно вивести той, який є лексикографічно найменшим.