eolymp
bolt
Try our new interface for solving problems
Problems

Гербарий

Гербарий

Time limit 1 second
Memory limit 16 MiB

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

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

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

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

Input data

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

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

Output data

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

Examples

Input example #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
Output example #1
9
Source Региональная олимпиада по программированию, СибГИУ, 2011