E. Миша и раскраски
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Миша нашел квадратную матрицу $$$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, 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$$$.

Пожалуйста, найдите минимальное количество операций, которые нужны, чтобы Миша достиг своей цели.

Входные данные

В первой строке находятся числа $$$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$$$-й строки матрицы.

Выходные данные

Выведите одно число — искомое минимальное число операций.

Примеры
Входные данные
3 4
1 1 1
1 1 2
3 4 5
Выходные данные
1
Входные данные
3 2
2 1 3
2 1 1
3 1 2
Выходные данные
2
Входные данные
3 3
1 1 1
1 1 2
2 2 2
Выходные данные
1
Входные данные
3 2
1 1 1
1 2 1
2 2 2
Выходные данные
0
Примечание

В первом примере ответ $$$1$$$, так как можно заменить число в правом нижнем углу таблички на $$$1$$$. Получится такая матрица:

111
112
341

Во втором примере ответ $$$2$$$. Можно сначала заменить все значения матрицы на $$$1$$$, а потом заменить число в любой клетке на $$$2$$$. Получится такая матрица:

111
111
112