Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

BitZero y BitOne han ideado un experimento que les ayudará a resolver grandes misterios sobre el surgimiento de BitLand, pero no tienen el presupuesto suficiente para desarrollarlo. Es necesario entonces ganar algunos BitCoins antes de hacer ciencia y para esto han decidido explotar sus minas de oro y plata.
Las minas se encuentran dentro de un terreno rectangular de $N \times M$ celdas cuadradas de igual tamaño. Algunas de estas celdas presentan irregularidades que hacen imposible el paso a través de ellas y otras contienen una mina de oro o de plata. Como BitZero y BitOne son muy buenos estadísticos, han decidido colocar estratégicamente lugares de trabajo en algunas de las celdas libres. Ahora solo falta contratar a los trabajadores para que extraigan el oro y la plata. BitZero ha decidido que a cada trabajador le corresponderá un único lugar de trabajo, además de trabajar en exactamente una mina de oro y en otra de plata. Cada mina puede ser explotada por a lo sumo un trabajador y un lugar de trabajo no puede estar asignado a más de un trabajador. Como restricción adicional, y debido al trabajo estadístico de BitOne sobre la eficiencia en la explotación de minas, el lugar de trabajo asignado a cada trabajador no puede estar a más de $K$ metros de las dos minas que le fueron asignadas. Los trabajadores sólo pueden caminar sobre las celdas vacías en sus recorridos y hacia una de las cuatro celdas adyacentes (arriba, abajo, izquierda y derecha) si existen. Dos celdas adyacentes están a un metro de distancia.
El problema que se plantean BitOne y BitZero ahora es cuál será la cantidad máxima de trabajadores que pueden contratar tal que se cumplan todas sus restricciones.

1ra línea : tres enteros $N$, $M$ $(1 \le N, M \le 30)$ y $K$ $(1 \le K \le 1000)$ que representan las dimensiones del terreno y la distancia máxima posible desde el lugar de trabajo de cada trabajador a cada una de las minas que le fueron asignadas.
N siguientes líneas : una cadena de $M$ caracteres, cada uno indicando el contenido de la celda correspondiente. Las letras 'G' y 'S' representan una mina de oro y de plata respectivamente, la letra 'W' indica un lugar de trabajo disponible, la letra 'X' indica una celda inaccesible (esencialmente porque hay imanes en ella y BitOne y BitZero le temen a los imanes porque los hacen sentir mareados) y '.' indica que la celda está vacía y que los trabajadores pueden caminar sobre ellas.

1ra línea : un entero indicando la cantidad máxima de trabajadores que pueden ser contratados.