Agrāk cilvēki nolasīja N*M kokvilnas laukus. Bet vienā dienā nepietiek laika nolasīt visus. Viņi varēja nolasīt tikai K laukus, kuru malas saskarās. Dēļ senām tradīcijām laukus varēja lasīt tikai ejot pa labi un uz leju. Lasīšanu sāka ar augšējo, kreiso stūri.

Vēstures pētniekus interesē, kāds ir maksimālais kokvilnas daudzums, kuru viņi varēja nolasīt vienas dienas laikā?

Doti 3 skaitļi 1 <= N <= 10³, 1 <= M <= 10³ un 1 <= K <= 10⁶

Tālāk seko N rindas ar M skaitļiem katrā rindā, kur katrs nepārsniedz 10⁹.

Jāizvada maksimālais kokvilnas daudzums, kuru agrīnie cilvēki var nolasīt vienas dienas laikā.

Dotajā piemērā agrīnie cilvēki novāca laukus secībā 1 → 6 → 11 → 16 → 21 → 22 → 23 .

• 10% testos N, M = 3, K = 5
• 20% testos 1 <= N,M <= 50
• 20% testos N+M-1 = K
• 50% bez papildus ierobežojumiem

Autors: Kaspars Kļaviņš