Задачі
Василько і матриця
Василько і матриця
Василькові мама подарувала прямокутну матрицю n на m. У кожній клітинці матриці є записано ціле число. Василько довго бавився у різні математичні ігри з нею: то швидко обчислював її детермінант, то з легкістю її підносив до різних степенів.
Але такі ігри йому трохи надоїли, тож він придумав для себе нову розвагу: він вибирає ціле число k, і намагається знайти підматрицю максимальної площі, в якій сума усіх чисел не перевищує k. Підматриця – це прямокутна ділянка матриці.
Вхідні дані
У першому рядку задано три цілих числа n, m i k (1 ≤ n,m ≤ 300, 1 ≤ k ≤ 10^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