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

Стрекоза и муравей

Стрекоза и муравей

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Сложные и многогранные взаимоотношения между стрекозой и муравьем отражены отнюдь не только в известной басне Крылова. В частности, согласно одноименной грузинской народной сказке, стрекоза выручает муравья, попавшего в реку до того, как тот успел научиться плавать. Кстати, о том как обстоят дела у муравья в этом смысле в данный момент, народный эпос пока умалчивает. Рассказ о том, как все же стрекоза сумела выручить муравья из беды, заслуживает отдельной задачи. Мы же проследим за событиями с того момента, когда спасенный муравей решил пригласить своего спасителя в лучшую хинкальную леса, в котором они обитали. В момент, когда муравью пришла в голову такая мысль, друзья находились на краю опушки, которую можно представить как прямоугольный участок размером M×N. Каждая клетка этого участка характеризуется своей высотой от уровня моря. При этом, друзья находятся в клетке (1, 1), а вожделенная хинкальная расположена на другом конце опушки в клетке (M, N). Каждым очередным шагом друзья могут попасть в любую из соседних клеток, расположенных внутри опушки. Две квадратные клетки считаются соседними, если у них есть общая сторона.

Перед друзьями стала задача подобрать такой маршрут, чтобы возможно меньше устать. Но как им быть, если для стрекозы предпочтителен маршрут, проходящий по меньшему количеству клеток, а для муравья – маршрут, в котором минимальна максимальная высота, на которую ему придется подняться. Начальная и конечная клетки входят в маршрут. Так как по версии грузинской народной сказки и стрекоза, и муравей хорошо воспитаны, то каждый из них настаивает на варианте, объективно предпочтительном для друга. И постольку поскольку мы пока еще не знаем, кто оказался более настойчивым, нам необходимо быть готовыми помочь друзьям при подборе маршрута в обоих возможных вариантах. Таким образом, нам необходимо определить длину пути, т.е. количество пройденных клеток, с учетом начальной и конечной, а также максимальную высоту, взятую по пути друзьями при условии, что:

  • был подобран маршрут, наиболее удобный для стрекозы, а в случае, если таких оказалось несколько, среди них был выбран маршрут, наилучшим образом отвечающий интересам муравья;

  • был подобран маршрут, наиболее удобный для муравья, а в случае, если таких оказалось несколько, среди них был выбран маршрут, наилучшим образом отвечающий интересам стрекозы.

Входные данные

Первая строка содержит значения чисел M и N. M и N – целые числа, причем 2M, N500.

Каждая из следующих M строк содержит по N чисел. j-ое число i+1–ой строки соответствует высоте клетки (i, j). Высота каждой клетки – это целое число, принадлежащее диапазону 1..1000000000 включительно.

Выходные данные

Две строки, каждая из которых содержит по два целых числа. В первой строке выводятся длина и максимальная высота маршрута для первого случая, а во втором соответствующие данные для второго случая.

Пример

Входные данные #1
4 5
2 3 2 1 2
1 4 1 4 2
2 1 2 3 2
1 2 1 4 1
Выходные данные #1
8 3
12 2
Автор Николоз Джимшелеишвили
Источник Зимняя школа, Харьков 2009, контест Теодора Заркуа и его учеников