Misha 有一个 $$$n \times n$$$ 方阵,其中行 $$$i$$$ 和列 $$$j$$$ 中的数字等于 $$$a_{i, j}$$$。 Misha 想要修改矩阵以恰好包含 $$$k$$$ 个不同的整数。为了实现这一目标,Misha 可以执行以下操作零次或多次:
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, y)$$$ 的单元格,使得 $$$x_1 \leq x \leq x_2$$$, $$$y_1 \leq y \leq y_2$$$),
2. 选择一个整数 $$$k$$$,其中 $$$1 \leq k \leq n^2$$$,
3. 将子矩阵中的所有整数替换为$$$k$$$。
请找出 Misha 实现目标所需的最少操作次数。
输入
第一个输入行包含两个整数 $$$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$$$ 行的元素。
输出
输出一个整数——所需的最少运算次数。
示例
输入 #1
3 4 1 1 1 1 1 2 3 4 5
输出 #1
1
输入 #2
3 2 2 1 3 2 1 1 3 1 2
输出 #2
2
输入 #3
3 3 1 1 1 1 1 2 2 2 2
输出 #3
1
输入#4
3 2 1 1 1 1 2 1 2 2 2
输出#4
0
注意
在第一个测试用例中,答案是 $$$1$$$,因为可以将矩阵右下角的值更改为 $$$1$$$。生成的矩阵如下所示:
111112341
在第二个测试用例中,答案是 $$$2$$$。首先,可以将整个矩阵更改为仅包含 $$$1$$$,并将任何单个单元格的值更改为 $$$2$$$。可能的结果矩阵之一如下所示:
111111112