Участок земли

Город разбит на $N \times M$ клеток, известна цена каждой клетки. У вас $K$ денег. Купите прямоугольный участок наибольшей площади (числа клеток) с суммарной ценой не больше $K$. Если таких участков несколько, выберите самый дешёвый.

В первой строке $N$, $M$, $K$ ($1 \le N, M \le 100$, $0$). В каждой из следующих строк целых чисел — цены клеток ().

В одной строке два числа: площадь участка и его цена. Если нельзя купить ни одной клетки — 0 0.

Выберите верхнюю и нижнюю строки ($O(N^2)$ пар) — цена каждого столбца на этом участке берётся из префиксов столбцов за $O(1)$. Цены неотрицательны, поэтому по столбцам работают два указателя: для каждой правой границы найдите самую левую, при которой сумма $\le K$. Итого .