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

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

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

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

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

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

Единственная строка с парой целых чисел – длина и максимальная высота выбранного друзьями маршрута, соответственно.