Miruna a găsit pe fundul mării o matrice cu n linii şi m coloane având elementele numere naturale. Din motive necunoscute, Mirunel, prietenul misterios al Mirunei, vrea să afle care este latura celei mai mari submatrice pătratice care conţine maxim k numere distincte. Submatricea cu colţul stânga-sus (xs, ys) şi colţul dreapta-jos (xd, yd) este formată din toate elementele din matrice având indicele liniei în intervalul [xs, xd] şi indicele coloanei în intervalul [ys, yd].
Cerinţă
Scrieţi un program care să determine latura maximă a unei submatrice care respectă condiţiile lui Mirunel.
Date de intrare
Fişierul de intrare submatrix.in conţine pe prima linie trei numere naturale n, m şi k separate prin câte un singur spaţiu având semnificaţia din enunţ. Pe următoarele n linii se găsesc câte m numere naturale separate prin spaţiu, reprezentând elementele matricei.
Date de ieşire
Fişierul de ieşire submatrix.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând latura unei submatrice cu proprietatea din enunţ.
Restricţii şi precizări
1 ≤ n, m ≤ 3001 ≤ k ≤ n * m- Pentru
30%din teste1 ≤ n, m ≤ 30 - Pentru
70%din teste1 ≤ n, m ≤ 150
Exemple
submatrix.in
5 7 3
6 5 7 3 6 6 7
5 7 5 5 7 3 7
3 3 5 3 5 6 7
7 7 5 5 5 6 7
7 7 6 5 6 3 5
submatrix.out
3
Explicaţie
O soluţie este submatricea având colţul din stânga-sus pe poziţia (2, 3) şi latura 3, care conţine doar elementele 3, 5 şi 7.