EduBrick

Самый длинный подъём

8000 мс · 512 МБ · всё или ничего

В клетках поля написаны высоты. Из клетки можно перейти в соседнюю по стороне, если её высота строго больше.

Какой наибольшей длины путь можно пройти? Длина считается числом клеток.

Формат ввода

В первой строке числа nn и mm от 11 до 500500. В следующих nn строках по mm чисел от 109-10^9 до 10910^9.

Формат вывода

Одно число.

Примеры

ввод
1 1
5
вывод
1

Примечание

Состояние — «длина самого длинного подъёма, начинающегося в этой клетке». Порядок вычисления задаётся высотами: если считать от высоких клеток к низким, все нужные значения окажутся готовы. Рекурсия с запоминанием тоже подошла бы, но на поле в четверть миллиона клеток она упрётся в предел глубины.

Войдите, чтобы отправлять решения.