Школа#7096
Петро П'яточкін навчається у школі. Торік він їздив до школи тролейбусами, але після підвищення цін на проїзні квитки зрозумів, що швидше і зручніше добиратися пішки. Місто Ідеальне, де живе Петрик, — це прямокутник розміром m \times n кварталів, складений з однакових квадратних блоків. Межа міста проходить не вздовж межі кварталів, а ділить їх навпіл або "відрізає" від кутових кварталів чвертинки — див. схему міста на рис. 1.
Рис. 1. Схема міста Ідеальне. Межі міста позначено товстою чорною лінією.
Петрик вирушає до школи з найпівденнішого та одночасно найсхіднішого з кутів кварталів, що належать місту, і прямує до найпівнічнішого та найзахіднішого кута, де розташовано вхід до школи. Початковий та кінцевий пункти позначено на рис. 1 міста жирними крапками. Хлопець може пересуватися лише межами кварталів (самі квартали, ясна річ, забудовані) та переходити з вершини одного кварталу до вершини сусіднього лише перпендикулярно до напряму вулиці — паралельно межам міста. Для кожного перехрестя визначено тривалість горизонтального (зі сходу на захід і навпаки) та вертикального (з півночі на південь і назад) руху. Кожен світлофор працює так: протягом перших секунд світлофор дозволяє горизонтальний рух і забороняє вертикальний, протягом наступних дозволяє вертикальний (та забороняє горизонтальний), з (2t+1)-ї секунди до -ї знову дозволяє горизонтальний і так далі. Для різних перехресть ця величина може бути різною. Пройти один бік кварталу Петрик може за хвилину. Вулицю хлопець переходить за секунду — коли світлофор це дозволяє. Переходити ж на червоне світло та виходити за межі міста Петрик не хоче — це надто небезпечно.
Допоможіть Петрикові визначити, за який найкоротший проміжок часу він може дійти до школи. Відомо, що в момент, коли Петрик виходить з дому, всі світлофори саме дозволяють горизонтальний рух.
У першому рядку вказано натуральні числа та — ширину й висоту міста. Ці числа не перевищують .
Далі йдуть рядків. Для та таких, що 1 \leq i \leq n, 1 \leq j \leq m, -те число (i+1)-го рядка — це тривалість руху на відповідному перехресті. Це число натуральне та не перевищує . У кожному рядку перелічено перехрестя від найзахіднішого до найсхіднішого, у першому рядку описано найпівнічніші перехрестя, в останньому — найпівденніші.
Виведіть тривалість найменшого проміжку часу (у секундах), якого Петрикові достатньо, щоб дістатися до школи.
Приклад 1
Петрик може дістатися до школи за секунд: він вийде з дому й одразу перейде дорогу у горизонтальному напрямку; зачекає секунди, поки світлофор дозволить рух у вертикальному напрямку, і перейде дорогу на північ; дістанеться протилежного кута кварталу за секунд і, оскільки відповідний світлофор дозволятиме горизонтальний рух, одразу ж перейде вулицю та продовжуватиме рух у східному напрямку, поки не дійде до наступного перехрестя. Він встигне перейти вулицю у вертикальному напрямку в останню секунду, коли світлофор дозволяє це робити, і відразу ж востаннє перейде дорогу та дістанеться до школи. Шлях Петрика позначено на схемі. Число в куті кварталу на схемі позначає кількість секунд, яку Петрику необхідно витратити, щоб дістатися до цього кута.
Легко побачити, що швидше ніж за секунд хлопець до школи не потрапить. Справді, якби Петрику взагалі не доводилося чекати на зелене світло, він міг би дістатися до школи щонайшвидше за секунд (він мав би тричі пройти вздовж кварталів та п'ять разів перейти вулицю). З іншого боку, перед тим як уперше перейти вулицю у північному напрямку — хай скільки кварталів він пройде на схід — хлопцю потрібно чекати щонайменше секунди.
Рис. 2. Один із оптимальних шляхів Петрика до школи для поданого прикладу вхідних даних.