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

Василько і матриця

Василько і матриця

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Василькові мама подарувала прямокутну матрицю n на m. У кожній клітинці матриці є записано ціле число. Василько довго бавився у різні математичні ігри з нею: то швидко обчислював її детермінант, то з легкістю її підносив до різних степенів.

Але такі ігри йому трохи надоїли, тож він придумав для себе нову розвагу: він вибирає ціле число k, і намагається знайти підматрицю максимальної площі, в якій сума усіх чисел не перевищує k. Підматриця – це прямокутна ділянка матриці.

Вхідні дані

У першому рядку задано три цілих числа n, m i k (1n,m300, 1k10^9).

У наступних n рядках задано по m невід’ємних цілих чисел, кожне з яких не перевищує 1000.

Вихідні дані

Виведіть єдине число – площу максимальної підматриці, сума чисел в якій не перевищує k.

Приклад

Вхідні дані #1
1 3 4
8 6 4
Вихідні дані #1
1
Вхідні дані #2
3 3 12
7 5 7
8 4 8
4 3 2
Вихідні дані #2
3