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$$$.
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.
Line $$$1$$$: The minimum time needed for the car to reach or drive through an ending point.
5 5 1 S.... #.#.E ..### ..E## .####
5