kredit

Profesor Djuri?: Haloooo!<br>
Dragan?e: Dobar dan, profesore, Dragan?e je ovde.<br>
Profesor Djuri?: šta raaadiš, mom?ino?<br>
Dragan?e: Upravo šetam parkom, i kad sam stigao do fontane, dobio sam ideju za onaj zadatak o kome smo ju?e diskutovali...<br>
Profesor Djuri?: A jeeee li.<br><br>

Tako se nastavio telefonski razgovor, koji je trajao K minuta, i ko zna koliko bi još trajao da Dragan?etu nije nestalo kredita. Dragan?e je odmah krenuo da kupi dodatni kredit, pošto zna lokacije svih trafika u parku, i krenuo je u onu do koje mu treba najmanje vremena. ?im stigne i uplati kredit, pozva?e profesora ponovo. Profesor Djuri? želi da kvalitetno organizuje svoje vreme i potrebna mu je procena koliko Dragan?etu treba vremena da ponovo pozove.<br><br>

Ulaz:<br><br>

(Ulazni podaci se ucitavaju sa standardnog ulaza) I Djuri? i Dragan?e ta?no znaju mapu parka, koja je data u obliku pravougaone matrice dimenzija N x M, gde su N i M brojevi zadati u prvom redu ulaza. U drugom redu je broj K. U svakom od narednih N redova se nalazi po M znakova, koji ozna?avaju polja na mapi. Dozvoljeni znakovi su 'F', 'x', '.' i 'T'. Znak 'F' ozna?ava fontanu. Sve prepreke (npr. jezero, stadion, cve?e...) ozna?ene su sa 'x', dok su sa '.' ozna?eni delovi parka slobodni za šetnju. Sa 'T' su tako?e ozna?eni delovi parka gde se može pro?i, i u njima se nalazi trafika gde se može uplatiti kredit. Dragan?e se na po?etku razgovora nalazi kod fontane. U jednom minutu on može pre?i u neko od susednih polja (istok, zapad, sever ili jug), a može ostati i tu gde jeste. U toku razgovora on se šeta nasumi?no. Kada bude krenuo do trafike, ne?e praviti pauze, ve? i?i najkra?im putem dok ne stigne do nje.<br><br>

Izlaz:<br><br>

(Izlazne podatke upisati na standardni izlaz) Profesor Djuri? ne zna gde se Dragan?e šetao u toku razgovora i želi da proceni minimalno i maksimalno vreme koje je potrebno Dragan?etu da do?e do trafike sa kreditom. U jedinom redu izlazne datoteke treba ispisati dva broja, MIN i MAX, odvojena razmakom; oni ozna?avaju minimalni i maksimalni broj minuta potreban da Dragan?e stigne do neke od trafika.<br><br>

Ograni?enja:<br><br>

* brojevi N i M nisu ve?i od 200<br>
* K nije ve?e od 500<br>
* broj trafika nije ve?i od 1000<br>
* znak 'F' se nalazi ta?no jednom u ulaznoj datoteci<br>
* Park je takav da Dragan?e uvek može sti?i do neke od trafika. U delu sa fontanom se ne nalazi trafika.<br><br>

Napomena:<br><br>

Ako je barem jedan od brojeva MIN ili MAX ta?an, dobi?ete 50% poena za taj primer.<br><br>

Primeri:<br><br>
Ulaz:<br>
<pre>
5 5
3
x..xF
.x...
T..x.
x.T..
...T.
</pre>

Izlaz:<br>
2 5<br><br>

Objašnjenje:<br><br>

Posle 3 minuta razgovora, Dragan?e ?e mo?i da se približi nekoj od trafika i za samo 2 minuta stigne do nje, a mogu?e je i da ostane sve vreme kraj fontane, odakle ?e mu trebati 5 minuta do najbliže trafike.<br><br>