Fișierul intrare/ieșire	ssk.in, ssk.out	Sursă	ONI 2015 baraj gimnaziu
Autor	Dana Lica	Adăugată de	Cella Florescu • cella.florescu
Timp de execuție pe test	1.2 sec	Limită de memorie	5120 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Ssk (baraj gimnaziu)

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

Exemplu