Nosaukums
Pārstādīšana (101)
Laika limits
0.20s
Atmiņas limits
32.0 MB
Grūtība
60%

Definīcija

Gudriniekam Pēterim negaršo dārzeņi, bet viņš vēlas sākt ievērot veselīgu dzīves veidu. Tādēļ viņš ir nolēmis vienreiz dienā iziet cauri savam dārzam un apēst tieši K dārzeņus. Lai nepieļautu kļūdas, katru reizi, skaitot līdzi, viņš ir nolēmis izveidot maršrutu, pa kuru ejot un apēdot tieši vienu dārzeni no katras dobes, viņa mērķis būtu piepildīts.

Dārzs ir taisnstūrveida formas, un sastāv no N rindām un M kolonām ar dobēm. Dobe ir vai nu tukša (apzīmēta ar 0), vai tajā aug dārzeņi (apzīmēta ar 1). Dārza ieeja ir kreisajā augšējā stūrī, bet izeja ir apakšējā labajā stūrī.

Pēteris nevēlas, lai šis ceļš būtu pārāk garš, tādēļ viņš ir nolēmis, ka maršrutā dosies tikai tikai pa labi vai uz leju, jeb no dobes ar koordinātēm (i, j) Pēteris var tālāk doties uz dobi (i + 1, j) vai (i, j +1). Apkārt dārzam ir žogs, tādēļ no dārza var iziet tikai caur izejas vārtiem.

Pēteris var paņemt jebkuru dobi un pamainīt 0 uz 1, vai 1 uz 0. Noskaidrojiet, kāds ir minimālais dobju skaits dārzā, kuras jāmaina, lai tajā varētu atrast Pētera maršrutu (ar tieši vieniniekiem).


Ievaddatu raksturojums

Pirmajā rindā doti trīs veseli skaitļi: N, M un K (2 ≤ N, M ≤ 1000, 0 ≤ K < N+M).

Nākamajās rindās seko dārza apraksts – N rindas ar M simboliem 0 vai 1.


Izvaddatu raksturojums

Izvadiet vienu veselu skaitli, minimālo dobju skaitu, kas jāmaina, lai eksistētu Pētera vēlamais ceļš.  


Paraugdati

Stdin
4 6 3
100000
000000
000000
000000
Stdout
2

Stdin
5 9 7
111011111
110111110
111001011
111011111
111101101
Stdout
1

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