Longest Ski Slope

Michael loves skiing because it is exhilarating. However, to gain speed, the slope must be downward and one must eventually climb back up or wait for a lift. Michael is interested in finding the longest ski slope in a given region. The region is represented by a 2D grid where each number denotes the height at that point.

A skier can move from a position to one of its four adjacent positions (up, down, left, right) if and only if the height strictly decreases.

For example, consider the following 5x5 grid:

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

One possible ski slope is \(24-17-16-1\), but a longer slope exists: \(25-24-23-\ldots-3-2-1\). Your task is to compute the length of the longest ski slope available in the region.

Note: If there are multiple paths, you only need to output the length of the longest valid path.

inputFormat

The input begins with two integers \(R\) and \(C\) (the number of rows and columns of the grid). This is followed by \(R\) lines, each containing \(C\) integers separated by spaces, representing the height values in the grid.

For example:

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

outputFormat

Output a single integer: the length of the longest ski slope (i.e. the maximum number of cells in a strictly descending path based on adjacent moves).

sample

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

19