Петя Пяточкин учится в школе. В прошлом году он ездил в школу троллейбусами, но после подорожания проездных билетов понял, что быстрее и удобнее добираться туда пешком. Город Идеальное, где живет Петя, представляет собой прямоугольник размером \textbf{m} × \textbf{n} кварталов, составленный из одинаковых квадратных блоков. Граница города проходит не вдоль границы кварталов, а делит их пополам или "отрезает" от угловых кварталов чвертинкы - см. схему города на рис \textbf{1}. \includegraphics{https://static.e-olymp.com/content/28/28743e2b7cd9c1d56a65ebb6885f7a208e211cf0.jpg} \textbf{Рис. 1}. Схема города Идеальное. Границы города обозначены грубой черной линией Петя отправляется в школу с южного и одновременно самого восточного угла квартала, принадлежащих городу, и направляется к северному и западному углу, где находится вход в школу. Начальный и конечный пункты обозначены на рис. \textbf{1} города жирными точками. Парень может передвигаться только в пределах кварталов (сами кварталы конечно же застроены) и переходить с вершины одного квартала на вершину соседнего только перпендикулярно направлению улицы - параллельно границам города. Для каждого перекрестка определена продолжительность \textbf{t} горизонтального (с востока на запад и наоборот) и вертикального (с севера на юг и обратно) движения. Каждый светофор работает так: в течение первых \textbf{t} секунд светофор позволяет горизонтальное движение и запрещает вертикальное, в течение следующих \textbf{t} секунд позволяет вертикальное (и запрещает горизонтальное), с (\textbf{2t} + 1)-ой секунды до \textbf{3t}-ой снова позволяет горизонтальное и так далее. Для различных перекрестков эта величина \textbf{t} может быть разной. Пройти одну сторону квартала Петя может за минуту. Улицу парень переходит за одну секунду - когда светофоры это позволяют. Переходить же на красный свет и выходить за пределы города Петя не хочет - это слишком опасно. Помогите Пете определить, за какой кратчайший промежуток времени он сможет дойти до школы. Известно, что в момент, когда Петя выходит из дома, все светофоры разрешают горизонтальное движение. \InputFile Первая строка содержит натуральные числа \textbf{m }и \textbf{n} - ширину и высоту города. Эти числа не превышают \textbf{250}. Дальше идут \textbf{n} строк. При \textbf{i }и \textbf{j }таких, что \textbf{1 }≤ \textbf{i }≤ \textbf{n}, \textbf{1 }≤ \textbf{j }≤ \textbf{m}, \textbf{j}-тое число (\textbf{i+1})-ой строки - это продолжительность движения на соответствующем перекрестке. Это число натуральное и не превышает \textbf{500}. В каждой строке перечислены перекрестки от западного до самого восточного, в первой строке описаны северные перекрестки, а в последнем - южные. \OutputFile Вывести продолжительность кратчайшего промежутка времени (в секундах), которого Пете достаточно, чтобы добраться до школы. \textbf{Пояснення до прикладу} Петрик може дістатись до школи за \textbf{187} секунд: він вийде з дому й одразу перейде дорогу в горизонтальному напрямі; зачекає \textbf{2} секунди, поки світлофор дозволить рух у вертикальному напрямі, й перейде дорогу на північ; дістанеться протилежного кута кварталу за \textbf{120} секунд і, оскільки відповідний світлофор дозволятиме горизонтальний рух, одразу ж перейде вулицю та продовжуватиме рух у східному напрямі, поки не дійде до наступного перехрестя. Він встигне перейти вулицю у вертикальному напрямі в останню секунду, коли світлофор дозволяє це робити, і зараз же востаннє перейде дорогу, та дістанеться до школи. Шлях Петрика позначено на схемі. Число в куті кварталу на схемі позначає кількість секунд, яку Петрику необхідно витратити, щоб дістатись до цього кута. Легко побачити, що швидше ніж за \textbf{187} секунд хлопець до школи не потрапить. Справді, якби Петрику взагалі не доводилось чекати на зелене світло, він міг би дістатись до школи щонайшвидше за \textbf{185} секунд (він мав би тричі пройти вздовж кварталів та п’ять разів перейти вулицю). З іншого боку, перед тим як уперше перейти вулицю в північному напрямі --- хай скільки кварталів він пройде в східному --- хлопцю потрібно чекати щонайменше \textbf{2} секунди. \includegraphics{https://static.e-olymp.com/content/f6/f6041e47c42f7b3a4463bd8268fe9cd8b4cc9936.jpg} \textit{\textbf{Рис. 2}}. Один з оптимальних шляхів Петрика до школи для поданого прикладу вхідних даних.