Mihnea cel Rău

În anul 1508, în timpul celei de-a doua domnii a lui Mihnea cel Rău în Țara Românească, domnitorul pornește într-o campanie de strângere a dărilor din sate. Țara este reprezentată sub forma unei hărți dreptunghiulare împărțite în $N$ rânduri și $M$ coloane, fiecare poziție corespunzând unui sat. Fiecare sat are o sumă de bani ce poate fi colectată, reprezentată printr-un număr natural: $A[i][j] =$ numărul de galbeni aflați în satul de pe rândul $i$ și coloana $j$. Mihnea dorește să aleagă o regiune compactă din țară, formată din sate alăturate, adică un subdreptunghi al matricei, cu laturile paralele cu marginile hărții. Domnitorul știe însă că dacă strânge prea mult dintr-o zonă, oamenii se vor răscula. De aceea își impune condiția: suma totală a galbenilor din regiunea aleasă trebuie să fie cel mult T.

Cerință

Cerința 1

Mihnea dorește să înceapă campania cu sate izolate, fără a colecta din regiuni mari. Se cere să se determine:câte sate (adică subdreptunghiuri de dimensiune $1 × 1$) conțin cel mult T galbeni. Cu alte cuvinte, se cere numărul de celule din matrice pentru care: $A[i][j] ≤ T$

Cerința 2

Mihnea are deja stabilită dimensiunea zonei pe care vrea să o cerceteze: $K$ rânduri și $L$ coloane. El vrea să afle câte subdreptunghiuri de dimensiune exact $K × L$ au suma elementelor $≤ T$. Se cere: determinați numărul de subdreptunghiuri $K × L$ cu sumă totală $≤ T$ .

Cerința 3

Mihnea vrea să aleagă o zonă cât mai mare, astfel încât să includă un număr maxim de sate, dar să respecte limita T. Se cere: determinați aria maximă (numărul maxim de celule) a unui subdreptunghi din matrice a cărui sumă a elementelor este $≤ T$.

Date de intrare

Fișierul domnitor.in conține:

• pe prima linie: $C$ $N$ $M$ $T$, unde:
  • $C \in \{1,2,3\}$ este cerința ce trebuie rezolvată
  • $N, M, T$ au semnificația din enunț
• dacă $C = 2$ , pe linia următoare se află două numere naturale: $K$ $L$
• pe următoarele $N$ linii se află câte $M$ numere naturale, reprezentând matricea $A$.

Date de ieșire

Fișierul domnitor.out va conține:

• dacă $C = 1$: un singur număr natural — numărul de sate cu valoare $≤ T$
• dacă $C = 2$: un singur număr natural — numărul de subdreptunghiuri $K \times L$ cu sumă $≤ T$
• dacă $C = 3$: un singur număr natural — aria maximă a unui subdreptunghi cu sumă $≤ T$

Restricții și precizări

• $1 \leq N, M \leq 300$
• $0 \leq A[i][j] \leq 1 \ 000 \ 000$
• $0 \leq T \leq 10^{12}$
• dacă $C = 2: 1 \leq K \leq N, 1 \leq L \leq M$

Exemplul 1

domnitor.in

1 4 5 3
1 2 1 0 3
2 3 0 1 1
1 1 1 1 1
4 0 0 2 1

domnitor.out

19

Explicație

Există $19$ sate care conțin cel mult $3$ galbeni.

Exemplul 2

domnitor.in

2 4 5 6
2 3
1 2 1 0 3
2 3 0 1 1
1 1 1 1 1
4 0 0 2 1

domnitor.out

4

Explicație

Există $4$ subdreptunghiuri de dimensiune $2 \times 3$ care au suma elementelor cel mult $6$.

Exemplul 3

domnitor.in

3 5 7 15
1 2 1 0 3 2 1
2 3 0 1 1 0 2
1 1 1 1 1 1 1
4 0 0 2 1 0 1
0 2 1 1 0 3 0

domnitor.out

16

Explicație

Un subdreptunghi de dimensiune $4 \times 4$ are suma elementelor $15$ și aria $16$, respectând condiția impusă de Mihnea. Nu există un dreptunghi cu arie mai mare care să respecte limita $T$.