Description

You are given an n×m grid, where each cell contains a positive integer. The integer at row i and column j is denoted as Ai,j​. You can start your walk from any cell in the grid and move in four cardinal directions: up, down, left, and right. However, there is a restriction on the movement: you can only move to a neighboring cell if its integer value is strictly smaller than the integer value of the cell you are currently standing on.

Input

• The first line contains two integers n and m, being the number of rows and columns of the grid maze.
• This is followed by n lines, each containing m integers, representing the grid values. The j-th integer in the i-th line represents Ai,j​.

Restrictions

For test 1 ~ 4

• n = 1
• 1 ≤ m ≤ 1000
• 1 ≤ A_i,j ≤ 100000

For test 5 ~ 10

• 1 ≤ n, m ≤ 1000
• 1 ≤ A_i,j ≤ 100000

Output

output a single integer, the length of the longest path you can traverse starting from any cell and following the movement constraints.

Remember there should be a ‘\n’ at the end of the last line of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss