Петро П’яточкін учиться в школі. Торік він їздив до школи тролейбусами, але після подорожчання проїзних квитків збагнув, що швидше і зручніше діставатись туди пішки. Місто Ідеальне, де мешкає Петрик,--- це прямокутник завбільшки \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}-ї знову дозволяє горизонтальний і т. д. \textit{Для різних перехресть ця величина }\textit{\textbf{t}}\textit{ може бути різною}. Пройти один бік кварталу Петрик може за хвилину. Вулицю хлопець переходить за секунду --- коли світлофори це дозволяють. Переходити ж на червоне світло та виходити за межі міста Петрик не хоче --- це надто небезпечно. Допоможіть Петрикові визначити, за який найкоротший проміжок часу він може дійти до школи. Відомо, що в момент, коли Петрик виходить з дому, всі світлофори саме дозволяють горизонтальний рух. \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}}. Один з оптимальних шляхів Петрика до школи для поданого прикладу вхідних даних.