Стрекоза и муравей
Сложные и многогранные взаимоотношения между стрекозой и муравьем отражены отнюдь не только в известной басне Крылова. В частности, согласно одноименной грузинской народной сказке, стрекоза выручает муравья, попавшего в реку до того, как тот успел научиться плавать. Кстати, о том как обстоят дела у муравья в этом смысле в данный момент, народный эпос пока умалчивает. Рассказ о том, как все же стрекоза сумела выручить муравья из беды, заслуживает отдельной задачи. Мы же проследим за событиями с того момента, когда спасенный муравей решил пригласить своего спасителя в лучшую хинкальную леса, в котором они обитали. В момент, когда муравью пришла в голову такая мысль, друзья находились на краю опушки, которую можно представить как прямоугольный участок размером M×N. Каждая клетка этого участка характеризуется своей высотой от уровня моря. При этом, друзья находятся в клетке (1, 1), а вожделенная хинкальная расположена на другом конце опушки в клетке (M, N). Каждым очередным шагом друзья могут попасть в любую из соседних клеток, расположенных внутри опушки. Две квадратные клетки считаются соседними, если у них есть общая сторона.
Перед друзьями стала задача подобрать такой маршрут, чтобы возможно меньше устать. Но как им быть, если для стрекозы предпочтителен маршрут, проходящий по меньшему количеству клеток, а для муравья – маршрут, в котором минимальна максимальная высота, на которую ему придется подняться. Начальная и конечная клетки входят в маршрут. Так как по версии грузинской народной сказки и стрекоза, и муравей хорошо воспитаны, то каждый из них настаивает на варианте, объективно предпочтительном для друга. И постольку поскольку мы пока еще не знаем, кто оказался более настойчивым, нам необходимо быть готовыми помочь друзьям при подборе маршрута в обоих возможных вариантах. Таким образом, нам необходимо определить длину пути, т.е. количество пройденных клеток, с учетом начальной и конечной, а также максимальную высоту, взятую по пути друзьями при условии, что:
был подобран маршрут, наиболее удобный для стрекозы, а в случае, если таких оказалось несколько, среди них был выбран маршрут, наилучшим образом отвечающий интересам муравья;
был подобран маршрут, наиболее удобный для муравья, а в случае, если таких оказалось несколько, среди них был выбран маршрут, наилучшим образом отвечающий интересам стрекозы.
Входные данные
Первая строка содержит значения чисел M и N. M и N – целые числа, причем 2 ≤ M, N ≤ 500.
Каждая из следующих M строк содержит по N чисел. j-ое число i+1–ой строки соответствует высоте клетки (i, j). Высота каждой клетки – это целое число, принадлежащее диапазону 1..1000000000 включительно.
Выходные данные
Две строки, каждая из которых содержит по два целых числа. В первой строке выводятся длина и максимальная высота маршрута для первого случая, а во втором соответствующие данные для второго случая.