Школа
Петя Пяточкин учится в школе. В прошлом году он ездил в школу троллейбусами, но после подорожания проездных билетов понял, что быстрее и удобнее добираться туда пешком. Город Идеальное, где живет Петя, представляет собой прямоугольник размером m × n кварталов, составленный из одинаковых квадратных блоков. Граница города проходит не вдоль границы кварталов, а делит их пополам или "отрезает" от угловых кварталов чвертинкы - см. схему города на рис 1.
Рис. 1. Схема города Идеальное. Границы города обозначены грубой черной линией
Петя отправляется в школу с южного и одновременно самого восточного угла квартала, принадлежащих городу, и направляется к северному и западному углу, где находится вход в школу. Начальный и конечный пункты обозначены на рис. 1 города жирными точками. Парень может передвигаться только в пределах кварталов (сами кварталы конечно же застроены) и переходить с вершины одного квартала на вершину соседнего только перпендикулярно направлению улицы - параллельно границам города. Для каждого перекрестка определена продолжительность t горизонтального (с востока на запад и наоборот) и вертикального (с севера на юг и обратно) движения. Каждый светофор работает так: в течение первых t секунд светофор позволяет горизонтальное движение и запрещает вертикальное, в течение следующих t секунд позволяет вертикальное (и запрещает горизонтальное), с (2t + 1)-ой секунды до 3t-ой снова позволяет горизонтальное и так далее. Для различных перекрестков эта величина t может быть разной. Пройти одну сторону квартала Петя может за минуту. Улицу парень переходит за одну секунду - когда светофоры это позволяют. Переходить же на красный свет и выходить за пределы города Петя не хочет - это слишком опасно.
Помогите Пете определить, за какой кратчайший промежуток времени он сможет дойти до школы. Известно, что в момент, когда Петя выходит из дома, все светофоры разрешают горизонтальное движение.
Входные данные
Первая строка содержит натуральные числа m и n - ширину и высоту города. Эти числа не превышают 250.
Дальше идут n строк. При i и j таких, что 1 ≤ i ≤ n, 1 ≤ j ≤ m, j-тое число (i+1)-ой строки - это продолжительность движения на соответствующем перекрестке. Это число натуральное и не превышает 500. В каждой строке перечислены перекрестки от западного до самого восточного, в первой строке описаны северные перекрестки, а в последнем - южные.
Выходные данные
Вывести продолжительность кратчайшего промежутка времени (в секундах), которого Пете достаточно, чтобы добраться до школы.
Пояснення до прикладу
Петрик може дістатись до школи за 187 секунд: він вийде з дому й одразу перейде дорогу в горизонтальному напрямі; зачекає 2 секунди, поки світлофор дозволить рух у вертикальному напрямі, й перейде дорогу на північ; дістанеться протилежного кута кварталу за 120 секунд і, оскільки відповідний світлофор дозволятиме горизонтальний рух, одразу ж перейде вулицю та продовжуватиме рух у східному напрямі, поки не дійде до наступного перехрестя. Він встигне перейти вулицю у вертикальному напрямі в останню секунду, коли світлофор дозволяє це робити, і зараз же востаннє перейде дорогу, та дістанеться до школи. Шлях Петрика позначено на схемі. Число в куті кварталу на схемі позначає кількість секунд, яку Петрику необхідно витратити, щоб дістатись до цього кута.
Легко побачити, що швидше ніж за 187 секунд хлопець до школи не потрапить. Справді, якби Петрику взагалі не доводилось чекати на зелене світло, він міг би дістатись до школи щонайшвидше за 185 секунд (він мав би тричі пройти вздовж кварталів та п’ять разів перейти вулицю). З іншого боку, перед тим як уперше перейти вулицю в північному напрямі — хай скільки кварталів він пройде в східному — хлопцю потрібно чекати щонайменше 2 секунди.
Рис. 2. Один з оптимальних шляхів Петрика до школи для поданого прикладу вхідних даних.