최장 증가 부분 수열

정휘는 정수로 이루어진 $N\times N$ 크기의 배열에서 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸까지 최단 경로로 이동하려고 한다. 칸에서 다른 칸으로 이동할 때는 변을 공유하는 칸으로만 이동할 수 있다.

정휘는 이동하면서 만난 정수들을 순서대로 모아 성현이에게 선물로 주려고 한다. 성현이는 증가하는 부분 수열의 길이가 긴 수열을 좋아하기 때문에, 정휘는 최장 증가 부분 수열의 길이가 최대가 되는 수열을 만들어 주려고 한다.

정휘는 문제를 만들어야 해서 경로를 찾을 여유가 없다. $N\times N$ 크기의 배열이 주어졌을 때, 만들 수 있는 수열 중 최장 증가 부분 수열의 길이의 최댓값을 대신 구해 보자.

첫째 줄에 $N$이 주어진다. ($1 \leq N \leq 100$)

이어서 $N$개의 줄에 각각 $N$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 $1$ 이상 $10\,000$ 이하이다.

최장 증가 부분 수열의 길이의 최댓값을 출력한다.

• Python 사용자는 PyPy로 제출하는 것을 권장한다.
• 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열해서 얻은 수열을 말한다.
• 증가하는 부분 수열이란 맨 처음 원소를 제외한 모든 원소가 바로 앞 원소보다 큰 수열을 말한다. 즉, 길이가 $N$인 부분 수열 $A$가 $2 \leq i \leq N$인 모든 $i$에 대해 $A_{i-1} < A_i$를 만족하면, $A$는 증가하는 부분 수열이다.
• 최장 증가 부분 수열이란 주어진 수열의 증가하는 부분 수열 중 길이가 가장 긴 것을 의미한다.