eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Школа

Школа

Ліміт часу 1 секунда
Ліміт використання пам'яті 32 MiB

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

Приклад

Вхідні дані #1
3 2
1 2 3
3 5 6
Вихідні дані #1
187