CF1720E.Misha and Paintings

Misha has a square $n \times n$ matrix, where the number in row $i$ and column $j$ is equal to $a_{i, j}$. Misha wants to modify the matrix to contain exactly $k$ distinct integers. To achieve this goal, Misha can perform the following operation zero or more times:

1. choose any square submatrix of the matrix (you choose $(x_1,y_1)$, $(x_2,y_2)$, such that $x_1 \leq x_2$, $y_1 \leq y_2$, $x_2 - x_1 = y_2 - y_1$, then submatrix is a set of cells with coordinates $(x, y)$, such that $x_1 \leq x \leq x_2$, $y_1 \leq y \leq y_2$),
2. choose an integer $k$, where $1 \leq k \leq n^2$,
3. replace all integers in the submatrix with $k$.

Please find the minimum number of operations that Misha needs to achieve his goal.

米沙有一个 $n \times n$ 的方阵，其中第 $i$ 行第 $j$ 列的数为 $a_{i, j}$。米沙希望修改该矩阵，使其恰好包含 $k$ 个互不相同的整数。为达成这一目标，米沙可以执行以下操作零次或多次：

1. 任选矩阵的一个正方形子矩阵（即选定 $(x_1,y_1)$ 和 $(x_2,y_2)$，满足 $x_1 \leq x_2$、$y_1 \leq y_2$ 且 $x_2 - x_1 = y_2 - y_1$；该子矩阵由所有满足 $x_1 \leq x \leq x_2$、$y_1 \leq y \leq y_2$ 的单元格 $(x, y)$ 构成）；
2. 选择一个整数 $k$，满足 $1 \leq k \leq n^2$；
3. 将该子矩阵中所有整数替换为 $k$。

请找出米沙达成目标所需的最少操作次数。

The first input line contains two integers $n$ and $k$ ($1 \leq n \leq 500, 1 \leq k \leq n^2$) — the size of the matrix and the desired amount of distinct elements in the matrix.

Then $n$ lines follows. The $i$-th of them contains $n$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$ ($1 \leq a_{i,j} \leq n^2$) — the elements of the $i$-th row of the matrix.

第一行输入包含两个整数 $n$ 和 $k$（$1 \leq n \leq 500$，$1 \leq k \leq n^2$）—— 分别表示矩阵的大小以及矩阵中期望的不同元素个数。

接下来是 $n$ 行。其中第 $i$ 行包含 $n$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$（$1 \leq a_{i,j} \leq n^2$）—— 表示矩阵第 $i$ 行的元素。

Output one integer — the minimum number of operations required.

输出一个整数——所需的最少操作次数。

In the first test case the answer is $1$, because one can change the value in the bottom right corner of the matrix to $1$. The resulting matrix can be found below:

1

1

1

1

1

2

3

4

1

In the second test case the answer is $2$. First, one can change the entire matrix to contain only $1$s, and the change the value of any single cell to $2$. One of the possible resulting matrices is displayed below:

1

1

1

1

1

1

1

1

2

在第一个测试用例中，答案为 $1$，因为可以将矩阵右下角的值修改为 $1$。得到的矩阵如下所示：

1

1

1

1

1

2

3

4

1

在第二个测试用例中，答案为 $2$。首先，可以将整个矩阵的所有元素都改为 $1$，然后将任意一个单元格的值改为 $2$。其中一个可能得到的矩阵如下所示：

1

1

1

1

1

1

1

1

2