#P0867. 小风的课(hard)

小风的课(hard)

题目描述

小风最近沉迷罗小黑战记,没时间整理自己的课程计划了,请你帮小风看看整理他的课程计划最少需要多少步。 小风的课程计划是一个二维方形数组,你可以进行任意步操作,每一步有两个选择:

1.将二维数组中的一列所有元素都向下移动一格,并把最下面那个元素放在第一个

2.把数组中的任意一个数字替换成另一个数字

请你计算将小风的课整理成这样的最小步数。

$$\begin{bmatrix} 1 & n+1 & . & . & .& (n-1)*n+1\\ 2 & n+2 & . & . &.& (n-1)*n+2\\ . & . & . & .&. & .\\ . & . & . & .&. & .\\ . & . & . & .&. & .\\ n & 2*n & . & .&. &n*n \end{bmatrix}$$

输入格式

输入一个n(1≤n≤2∗103 1\le n \le2*10^3 ),表示小风的课程计划的行和列

接下来n行,每行输入n个数字.表示小风的课程计划

所有输出都不超过int范围

输出格式

输出一个整数表示最小步数

样例

2
1 4
1 3
2