Yer maydoni

Shahar $N \times M$ ta katakka bo'lingan, har bir katakning narxi ma'lum. Sizda $K$ so'm bor. Umumiy narxi $K$ dan oshmaydigan, yuzi (kataklar soni) eng katta to'g'ri to'rtburchakli maydonni sotib oling. Bunday maydonlar bir nechta bo'lsa, eng arzonini tanlang.

Birinchi qatorda $N$, $M$, $K$ ($1 \le N, M \le 100$, $0$). Keyingi ta qatorning har birida ta butun son — kataklar narxi ().

Bitta qatorda ikki son: maydon yuzi va narxi. Birorta katak ham sotib olib bo'lmasa, 0 0.

Yuqori va pastki qatorlarni tanlang ($O(N^2)$ juftlik) — har bir ustunning shu oraliqdagi narxi ustun prefiksidan $O(1)$ da olinadi. Narxlar manfiy emas, shuning uchun ustunlar bo'yicha ikki ko'rsatkich ishlaydi: har bir o'ng chegara uchun yig'indi $\le K$ bo'ladigan eng chap chegarani toping. Jami .