H. Sunset Drifting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A car is so fast that the only way it can maneuver is by drifting. Each second, the car moves forward by $$$N$$$ squares, following which it may choose to turn left or right, or keep driving straight. The map, which is of width $$$W$$$ and height $$$H$$$, that the car drives on contains obstacles, which the car may never hit (for example, a car's path within a second cannot run through any obstacles or the boundary of the map). "." denotes road, "#" denotes obstacles, "S" denotes the starting point, and "E" denotes the possible ending points. When a car starts on S, it may start driving in any direction. Find the least time, in seconds, it takes from the car to reach or drive through an ending point. If there is no valid path, print $$$-1$$$.

Input

Line $$$1$$$: Three space separated integers $$$W$$$, $$$H$$$ ($$$1 \le W, H \le 10^3$$$), and $$$N$$$ ($$$1 \le N \le 20$$$).

Lines $$$2...H+1$$$: Strings of length $$$W$$$ representing each row of the map.

Output

Line $$$1$$$: The minimum time needed for the car to reach or drive through an ending point.

Example
Input
5 5 1
S....
#.#.E
..###
..E##
.####
Output
5