eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Гербарий

Гербарий

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

Школьнику задали собрать гербарий, в котором не менее K листьев разных типов деревьев. В распоряжении школьника роща, которая разделена на N рядов, в каждом из которых по M квадратных участков одного размера. На каждом участке растут деревья одного типа.

Школьник решил собрать гербарий на фрагменте рощи квадратной формы. При этом он хочет знать минимальное количество участков, которые требуется обойти.

Зная, на каком участке растут какие деревья, требуется написать программу, которая поможет определить минимальный фрагмент рощи квадратной формы, позволяющий собрать гербарий, и подсчитать количество участков в данном фрагменте.

Примечание: школьник обходит все участки квадратного фрагмента рощи.

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

Первая строка содержит три целых числа N, M, K разделенных пробелами (1N, M100, 1K10000).

Следующие N строк содержат по M неотрицательных целых чисел, разделенных пробелами. Каждое число характеризует тип деревьев, которые растет в i-ом ряду на j-ом месте (1iN, 1jM). Значение номера типа дерева не превышает 10^9.

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

Выходной файл должен содержать одно целое число – количество участков в минимальном фрагменте рощи квадратной формы, который достаточно обойти школьнику, чтобы собрать гербарий. Гарантируется, что есть хотя бы один квадратный фрагмент рощи, который подходит школьнику.

Пример

Входные данные #1
5 5 3
1 2 2 2 4
1 2 2 2 2
1 1 2 2 2
2 1 2 2 2
1 1 2 3 3
Выходные данные #1
9
Источник Региональная олимпиада по программированию, СибГИУ, 2011