Ер майдони

Шаҳар $N \times M$ та катакка бўлинган, ҳар бир катакнинг нархи маълум. Сизда $K$ сўм бор. Умумий нархи $K$ дан ошмайдиган, юзи (катаклар сони) энг катта тўғри тўртбурчакли майдонни сотиб олинг. Бундай майдонлар бир нечта бўлса, энг арзонини танланг.

Биринчи қаторда $N$, $M$, $K$ ($1 \le N, M \le 100$, $0$). Кейинги та қаторнинг ҳар бирида та бутун сон — катаклар нархи ().

Битта қаторда икки сон: майдон юзи ва нархи. Бирорта катак ҳам сотиб олиб бўлмаса, 0 0.

Юқори ва пастки қаторларни танланг ($O(N^2)$ жуфтлик) — ҳар бир устуннинг шу оралиқдаги нархи устун префиксидан $O(1)$ да олинади. Нархлар манфий эмас, шунинг учун устунлар бўйича икки кўрсаткич ишлайди: ҳар бир ўнг чегара учун йиғинди $\le K$ бўладиган энг чап чегарани топинг. Жами .