MatriceInteresanta

Cerință

În urma petrecerii de ziua lui RAU-Gigel, copiii au primit atâtea bomboane încât au câștigat o energie debordantă – așa că l-au provocat pe RAU-Gigel la un concurs de … numărat!

Acestora li se dă o matrice cu $N$ linii și $M$ coloane, în care fiecare element este un număr natural nenul. Obiectivul lor este să determine câte submatrice (sub-dreptunghiuri formate din linii și coloane contigue) conțin exact $K$ valori distincte.

Date de intrare

Fișierul matriceinteresanta.in conține pe prima linie trei numere $N, M,$ respectiv $K$, având semnificația din enunț, iar pe următoarele $N$ linii câte $M$ numere separate prin câte un spațiu reprezentând elementele matricei.

Date de ieșire

Fișierul matriceinteresanta.out va conține pe prima linie un singur număr natural, reprezentând numărul de submatrice din matricea dată care conțin exact $K$ valori distincte.

Restricții și precizări

• $1 \leq N, M \leq 300$
• $1 \leq K \leq 50$
• Elementele din matrice sunt numere naturale nenule cu valoarea cuprinsă între $1$ și $50$
• Pentru teste în valoare de $30$ de puncte, $1 \leq N, M \leq 20$
• Pentru alte teste în valoare de $20$ de puncte, $1 \leq N, M \leq 40$
• Pentru alte teste în valoare de $15$ de puncte, $1 \leq N, M \leq 100$
• Pentru alte teste în valoare de $10$ de puncte, $1 \leq N, M \leq 200$
• Pentru restul testelor se păstrează restricțiile inițiale din enunț

Exemplul 1

matriceinteresanta.in

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

matriceinteresanta.out

6

Explicație

Submatricele căutate trebuie să aibă exact $3$ elemente distincte, deci singurele potrivite din exemplu sunt cele de dimensiune $1 \times 3$ sau $3 \times 1$, adică liniile și coloanele din matricea inițială, în total fiind $6$.

Exemplul 2

matriceinteresanta.in

3 3 3 
1 1 2
3 4 1
2 2 3

matriceinteresanta.out

7

Explicație

Un exemplu de submatrice care conține exact $3$ numere distincte este cea de dimensiune $2 \times 2$ din colțul stânga-jos, care conține elementele $3, 4, 2, 2$ (cele $3$ numere distincte fiind în acest caz $2, 3$ și $4$), iar exemple de submatrice care nu conțin exact $3$ numere sunt cea formată din totalitatea primelor $2$ linii (conține $4$ numere distincte) sau cea formată doar din ultima linie (conține $2$ numere distincte).