Longest Increasing Subsequence on a Grid Path

Jeonghwi wants to move from the top-left cell to the bottom-right cell of an $N\times N$ array of integers along a shortest path. He can only move between cells that share an edge.

While moving, Jeonghwi collects the integers he passes, in order, and gives them to Seonghyeon as a gift. Seonghyeon likes sequences with a long increasing subsequence, so Jeonghwi wants to build a sequence whose longest increasing subsequence is as long as possible.

Jeonghwi has no time to find the path because he is writing a problem. Given the $N\times N$ array, find the maximum possible length of the longest increasing subsequence among all sequences he can build.

The first line contains $N$ ($1 \leq N \leq 100$).

Each of the next $N$ lines contains $N$ integers separated by spaces. Each integer is between $1$ and $10\,000$, inclusive.

Print the maximum possible length of the longest increasing subsequence.

• Python users are recommended to submit with PyPy.
• A subsequence is a sequence obtained by picking one or more elements from the given sequence and listing them in their original order.
• An increasing subsequence is a sequence in which every element except the first is greater than the element right before it. In other words, for a subsequence $A$ of length $N$, if $A_{i-1} < A_i$ holds for every $2 \leq i \leq N$, then $A$ is an increasing subsequence.
• The longest increasing subsequence is the increasing subsequence of a given sequence that has the greatest length.