Marele Cercetător (zis MC) a descoperit pe planeta Csor un teren care-l va îmbogăti! Trimitând câtiva robotzi exploratori, MC are acum harta terenului, dată sub forma unei matrice pătratice cu n linii si n coloane. În această matrice se găseste la fiecare pozitie unul dintre caracterele 'x' (obstacol), 'o' (zonă liberă) sau '$' (aur). Prin pozitiile marcate cu 'x' un robot nu poate trece. MC are la dispozitie un număr nelimitat de robotzi-culegători pe care îi poate programa să plece de la pozitia (1,1) din matrice, deci coltul din stânga-sus. Robotzii care trec printr-o pozitie marcată cu '$' pot culege aurul de acolo. Un robot se deplasează numai în jos sau spre dreapta, deci dacă se află la o pozitie (i,j) poate trece apoi fie în pozitia (i+1,j), fie în pozitia (i,j+1), cu conditia să nu iasă din matrice. Problema este că aceste miscări sunt valabile numai dacă robotzii se află la una dintre primele p coloane ale matricei. Dacă însă robotzii se află la coloanele p+1..n, atunci ei se miscă numai în sus si spre dreapta, deci din pozitia (i,j) se deplasează fie în (i-1,j), fie în (i,j+1). În final sunt recuperati doar robotii care reusesc să ajungă la pozitia (1,n) din matrice (coltul din dreapta-sus).
Cerinţă
Să se determine cantitatea maximă de aur pe care o poate obtine MC din terenul descoperit, stiind că are la dispozitie un număr nelimitat de robotzi si aurul îl are numai de la robotzii care au reusit să ajungă la pozitia (1,n).
Date de intrare
Fişierul de intrare robotzi.in conţine pe prima linie numerele naturale n si p separate prin spatiu. Pe următoarele n linii se află câte n caractere din multimea {'x','o','$'} reprezentând câte o linie din matrice (aceste linii din fisier nu contin niciun caracter spatiu).
Date de ieşire
Fişierul de ieşire robotzi.out va conţine un singur număr natural reprezentând cantitatea de aur pe care MC o poate obtine de pe teren.
Restricţii
2 <= n <= 1000
1 <= p < n
Pentru toate testele, pozitiile (1,1) si (1,n) sunt marcate cu ‘o’ sau cu ‘$’
Exemplu
robotzi.in
robotzi.out
Explicaţii
5 3
o$ooo
$o$oo
$xxxo
oo$oo
o$xo$
5
Pentru că p=3, pe primele trei coloane robotzii se deplasează numai în jos si dreapta, pe coloanele 4 si 5 robotzii se deplasează în sus si spre dreapta. Aur pot colecta de la pozitiile (2,1) (1,2) (2,3) (3,1) si (4,3). Mai sunt două pozitii unde se află aur. În pozitia (5,2) robotzii pot ajunge, dar de acolo nu se mai pot întoarce la pozitia (1,5). În pozitia (5,5) robotzii nu pot ajunge.
robotzi.in
robotzi.out
Explicaţii
3 2
ox$
xx$
$$$
0
Niciun robot nu poate ajunge la pozitia finală (1,3).