Nosaukums
Kokvilna (cotton)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
64%

Definīcija

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ā?


Ievaddatu raksturojums

Doti 3 skaitļi 1 <= N <= 103, 1 <= M <= 10un 1 <= K <= 106

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


Izvaddatu raksturojums

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


Piezīmes

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ņš


Paraugdati

Stdin
5 5 7
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Stdout
100

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.