Manole a învăţat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii şi M coloane. El numerotează liniile de la 1 la N şi coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Şirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.
Prin subtablou el înţelege o zonă dreptunghiulară din matricea A, identificată prin colţul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.
Cerinţă
Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din şirul ordonat al sumelor tuturor subtablourilor matricii A.
Date de intrare
Fişierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spaţiu, având semnificaţia din enunţ. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.
Date de ieşire
Fişierul de ieşire ssk.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.
Restricţii
• 1 ≤ N ≤ 150
• 1 ≤ M ≤ 150
• 1 ≤ K ≤ numărul de termeni din şirul ordonat
• 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N şi 1 ≤ j ≤ M
• Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1.
Exemple
ssk.in
ssk.out
Explicaţii
2 3 14
3 2 7
4 1 0
9
Şirul ordonat al tuturor sumelor subtablourilor matricei este
0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17
A patrusprezecea sumă este 9