Steve is playing Minecraft! (and breaking the 4th wall) However, he finds himself suddenly sucked into a giant portal! Now Steve finds himself stuck in a mysterious world with r rows and c columns (1 <= r, c <= 300) full of stone blocks indicated by 'W' and bedrock indicated by 'B'. Steve has lost all his inventory except for a stone pickaxe with k (0 <= k <= 132) remaining uses (if you're wondering about the number that's the durability of a stone pickaxe). Furthermore, Steve finds that there is a low bedrock celing so he cannot jump over (and past) blocks. Note that the pickaxe is required to mine through stone blocks but it cannot destroy bedrock.
Steve is currently at position 'S'. He can only walk up, down, left or right and not diagonally. Steve needs to get to the exit portal located at position 'E'. Steve can mine blocks but each block mined will deplete his pickaxe by 1 use. Your task is to find the minimum number of steps Steve needs to take to reach the portal since his cuboid legs aren't exactly easy to walk on.
Input
The first line of input contains 3 integers r, c and k.
The next r lines describe the terrain on the corresponding rows. 'S' represents the start, 'E' represents the portal, 'W' represents a stone block, 'B' represents bedrock and '.' represents empty space.
Output
Print out the minimum number of steps required for Steve to escape. If he is unable to, print -1.
Limits
Subtask 1 (11%): 1 ≤ r, c ≤ 20, k = 0
Subtask 2 (38%): 1 ≤ r, c ≤ 100, k ≤ 40
Subtask 3 (51%): 1 ≤ r, c ≤ 300, k ≤ 132
Subtask 4 (0%): Sample Testcases
Sample Input 1
5 5 1
S.WWW
.B.WW
BW...
WWW.W
WE...
Sample Output 1
9
Sample Input 2
5 5 0
S.WWW
.B.WW
BW...
WWW.W
WE...
Sample Output 2
-1