Недавно Миша нашел квадратную матрицу \(n \times n\), где в клетке на пересечении строки \(i\) и столбца \(j\) записано число \(a_{i, j}\). После этого Миша решил немного изменить матрицу, чтобы количество различных чисел в ней стало ровно \(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\)-й строки матрицы.
Выведите одно число — искомое минимальное число операций.
В первом примере ответ \(1\), так как можно заменить число в правом нижнем углу таблички на \(1\). Получится такая матрица:
Во втором примере ответ \(2\). Можно сначала заменить все значения матрицы на \(1\), а потом заменить число в любой клетке на \(2\). Получится такая матрица:
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
3 2 1 1 1 1 2 1 2 2 2
0
3500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач