P - PrekláDDka

Realitný trh so skladovými priestormi dostal tvrdú ranu v podobe novely zákona o žeriavovej bezpečnosti. Nielenže sa sprísnili pravidlá na kvalitu podlahy pre ich umiestnenie, ale aj celý svet prekladacích skladísk musel prijať novú jednotku miery. Niektoré lineárne parcely sa kvôli riedkej ožeriavovateľnosti stali nepredajnými a maklérom neostáva nič iné, len sa pokúsiť predávať väčšie plochy, hlboko pod súčasné luxusné ceny.
Náš klient kúpil parcelu s rozmermi M*N(políčok), nanajvýš štvrtina unesie žeriav, a znova v ňom potrebuje rozmiestniť žeriavy tak, aby vedel tovar prepraviť medzi dvomi koncovými polohami (rohmi).
Prekladanie žeriavmi funguje tak, že jeden žeriav tovar zdvihne z nejakého políčka, na ktoré dosiahne a vyloží na iné, tiež ale musí byť v jeho dosahu. Z tohto políčka ho musí vedieť zodvihnúť iný žeriav a posunúť ďalej. V súlade s novým zákonom sú políčka rozdelené do troch kategórií: zakázané, voľné len pre tovar a voľné bez obmedzenia. Navyše, políčko, kam sa rozhodnete postaviť žeriav nie je možné použiť ako prekladové.
Klient dostal ponuku výhodne nakúpiť žeriavy s dosahom R, no aj by chcel ušetriť a kúpiť len najmenšie možné množstvo.

Úloha

Pre daný popis skladu a dosah žeriava zistite najmenší počet žeriavov potrebný na preloženie tovaru z prvého políčka na posledné.

Vstup

Prvý riadok obsahuje čísla M,N a R, v ďalších N reťazec s M znakmi popisujúcimi sklad.

• # znamená zakázané políčko
• + znamená obmedzené políčko
• . znamená voľné políčko

1 ≤ R ≤ 10
1 ≤ M,N ≤ 64

Výstup

Výstupom programu je odpoveď na každú sadu na samostatnom riadku. Ak úloha nemá riešenie, vypíšte -1

Príklad

Vstup:

5 5 2
.#.##
#####
##+##
#####
##.#.

Výstup:

2