Varžu cirks

Uz pilsētu ir atbraucis ciemos slavenais varžu cirks. Cauri pilsētai tek upe, kas sadala to divās daļās. Vienā no upes krastiem sēž vardes - cirka kolektīvs. Kāds vardēm ir izstāstījis, ka otrā upes krastā ir circeņi. Circeņi ir kukaiņi, kas cirka vardēm ļoti garšo.

Taču upi šķērsot it nemaz nav viegli. Par laimi upes straume ir lēna, un upē ir izauguši ūdensaugi. Ir iespējams, ka vardes var pārlēkt uz otru upes krastu, lecot pa ūdensaugiem. Veicot situācijas analīzi, vardes noskaidro, ka ūdensaugs noslīkst īsi pēc lēciena uz tā. Vardes secina, ka vienu ūdensaugu var izmantot ne vairāk kā viena varde.

Vardes nevar aizlēkt tālāk par $R$ vienībām. Citiem vārdiem, lēciens ir ierobežots ar rādiusu $R$. Lēciens ir ierobežots ar Eiklīda attālumu, kas ir nogriežņa garums starp lēciena sākumpunktu un beigu punktu. Zināms, ka upe ir plata, un vardes nevar pārlēkt vienā lēcienā pār visu upi, proti, ja $M$ ir upes platums, tad $M>R$. Vardes var upes krastos izvēlēties pozīcijas, no kuras sākt lēkt un uz kuru aizlēkt.

Upi un ūdensaugu izvietojumu tajā var aprakstīt kā $N \times M$ rūtiņu laukumu, kur $N$ - rindu skaits, un $M$ - kolonnu skaits. Attēlā redzama rūtiņu laukuma ilustrācija. Laukumā ar izmēriem $3 \times 6$ ($N=3$, $M=6$) ir pieci ūdensaugi. Šo ūdensaugu koordinātas ir $(2,1), (5,1), (4,2), (2,3), (5,3)$. Varde var sākt lēkt no kreisā krasta - kādas pozīcijas $(0, y)$, kur $y$ ir naturāls skaitlis no $1$ līdz $N$. Pretējais krasts ir attiecīgi visas pozīcijas $M+1=7$. kolonnā. Ja vardes lēciena rādiuss $R$ ir, piemēram, $\sqrt{5}$, tad pāri upei varēs pārlēkt tikai viena varde, bet ja $R<\sqrt{5}$, tad līdz otram krastam nevar aizlēkt neviena varde.

Palīdzi cirka kolektīvam noskaidrot, kāds ir lielākais varžu skaits, kas var pārlēkt uz otru upes krastu! Vardēm nerūp, vai tās varēs pēc tam arī atlēkt atpakaļ, jo otrā krastā ir ļoooooti gardi circeņi.

Pirmajā rindā doti trīs naturāli skaitļi - $N$ (rindu skaits, $1 \leq N \leq 20$), $M$ (kolonnu skaits, $1 \leq M \leq 20$) un $R^2$ (vardes lēciena garums kvadrātā, $1 \leq R^2 \leq 50$ un $R<M$). Starp katriem diviem blakus skaitļiem ir tukšumzīme.

Tālāk seko $N$ rindas, kas katra sastāv no $M$ laukumu raksturojošiem simboliem. Laukumā ar «@» ir apzīmētas rūtiņas, kurās ir ūdensaugs. Visas pārējās rūtiņas ir tukšas - tās ir apzīmētas ar «.».

Vienīgajā rindā ir jāizvada vesels nenegatīvs skaitlis - lielākais varžu, kas var pārlēkt uz otru upes krastu, skaits, ja vardes izvēlas lēkšanas ceļus optimāli.