Вам дана матрица из n строк и m столбцов, заполненная натуральными числами. По матрице можно перемещаться, из клетки можно уходить только в соседнюю по стороне клетку, переходы по диагонали, а также выход за границу матрицы запрещены.
Ваша задача — найти наиболее длинный возрастающий путь в матрице. Путь возрастающий, если значения в посещаемых клетках строго возрастают от начала пути к его концу.
В первой строке даны два числа, описывающие размер матрицы — n,m (1 ≤ n,m ≤ 103). В следующих n строках записана сама матрица. i-я строка матрицы содержит m чисел, записанных через пробел. Все элементы матрицы — натуральные числа, не превосходящие 109.
Выведите единственное число — длину наибольшего возрастающего пути.
|
2 3 10 8 5 10 5 4 |
4 |
|
2 2 1 1 1 1 |
1 |
|
2 2 10 9 9 11 |
2 |