Бабка та мураха 2
Складні та багатогранні взаємовідносини між бакою та мурахою відображені зовсім не лише у відомій байці Крилова. Зокрема, згідно однойменної грузинської народної казки, бабка виручає мураху, який попав у річку до того, як той встиг навчитись плавати. Доречіи, про те як обстоять справи у мурахи у цьому змісті в даний момент, народный епос поки що замовчує. Розповідь про те, як усе ж бабка зуміла виручити мураху з біди, заслуговоує окремої задачі. Ми ж прослідкуємо за подіями з того моменту, коли врятована мураха вирішила запрости свого спасителя у найкращу хінкальну в лісі, у якому вони мешкали. У момент, коли мурасі прийшла до голови така думка, друзі знаходились на краю узлісся, яке можна подати як прямокутну ділянку розміром M×N. Кожна клітинка цієї ділянки характеризується своєй висотою над рівнем моря. При цьому, друзі знаходяться у клітинці (1, 1), а бажана хінкальна розміщена на іншому кінці узлісся у клітинці (M, N). Кожним черговим кроком друзі можуть потрапити у довільну з сусідніх клітинок, розміщених всередині узлісся. Дві квадратні клітинки вважаються сусідніми, якщо у них є спільна сторона.
Перед друзями постала задача підібрати такий маршрут, щоб якомога менше втомитись. Але як їм бути, якщо для баки більш бажаний маршрут, який проходить по меншій кількості клітинок, а для мурахи – маршрут, у якому мінімальна максимальна висота, на яку їй доведеться піднятись. Початкова та кінцева клітинки входять у маршрут. Так як за версією грузинської народної казки і бабка, і мураха гарно виховані, то кожен з них наполягає на варіанті, об'єктивно переважнішому для друга. Але враховуючи, що це мураха запросила бабку, а не навпоки, вона наполягла, щоб було підібрано маршрут, найбільш зручний для бабки. У випадку, якщо таких виявилось декілька, серед них було вибрано маршрут, який найкращим чином відповідає інтересам мурахи.
Вхідні дані
Перший рядок містить значення чисел M та N. M та N – цілі числа, причому 2 ≤ M, N ≤ 500.
Кожен з наступних M рядків містить по N чисел. j-те число i+1–го рядка відповідає висоті клітинки (i, j). Висота кожної клітинки – це ціле число, яке належить діапазону 1..1000000000 включно.
Вихідні дані
Єдиний рядок з парою цілих чисел – довжина та максимальна висота вибраного друзями маршруту, відповідно.