DreptMax

Cerință

Se dă o matrice cu $n$ linii și $m$ coloane, ale cărei elemente sunt numere întregi nenegative.
Pentru fiecare celulă $(i, j)$ definim:

$Value(i, j) =$ aria maximă a unui dreptunghi cu colțul stânga-sus fixat în $(i, j)$, astfel încât suma elementelor din dreptunghi să fie mai mică sau egală cu $k$.

Se cere să se afișeze

Date de intrare

Pe prima linie se află trei numere întregi $n$, $m$ și $k$.
Pe următoarele $n$ linii se află câte $m$ numere întregi, separate prin spații, reprezentând elementele matricei.

Date de ieșire

Pe prima linie a fișierului de ieșire dreptmax.out se va găsi un singur număr întreg, reprezentând suma cerută în enunț.

Restricții și precizări

• $1 \le n, m \le 2\ 000$
• $0 \le k \le 5\ 000$
• $0 \le \text{mat}[i][j] \le 100$

Exemplul 1

dreptmax.in

5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

dreptmax.out

100

Exemplul 2

dreptmax.in

9 7 45
0 8 1 8 3 6 5
8 4 2 4 1 4 6
5 4 1 5 4 0 3
1 3 1 8 7 6 1
1 6 0 1 6 6 7
4 8 2 6 3 8 1
3 6 3 2 2 7 1
8 7 0 7 7 1 8
7 8 7 5 6 8 2

dreptmax.out

545