Deadly Rain

Time limit1.5sMemory limit1024 MB

Summary

Find the fewest moves from S to E on an N by N grid while managing umbrellas with durability and health, where rain hits every cell except S and E.

Level: Hard8 of 10
Topics: BFS, Bit manipulation, Graph
Solved: No attempts yet

Problem

A square grid has sides of length $N$ . Death rain falls on every cell except two: your current position and the safe zone. Rain is also about to fall on your current position, so you must cross the death rain and reach the safe zone quickly.

The grid contains $K$ umbrellas that block the rain for a while. Each umbrella has durability $D$ , and all umbrellas have the same durability. When you are rained on while holding an umbrella, its durability drops by 1. The umbrella disappears when its durability reaches 0.

Each move proceeds in this order:

Move up, down, left, or right. You cannot move outside the grid.
If you moved onto the safe zone, stop.
If you moved onto a cell with an umbrella, pick it up. If you already hold an umbrella, discard it and take the new one. A discarded umbrella can no longer be used.
If you are rained on, durability drops by 1 when you hold an umbrella. Otherwise, your health drops by 1.
If the umbrella's durability reaches 0, it disappears.
If your health reaches 0, you die.
If you still have health, repeat the steps above until you reach the safe zone.

Find the minimum number of moves needed to reach the safe zone from your current position.

Input

The first line contains $N$ , your current health $H$ , and the umbrella durability $D$ , separated by spaces.

The next $N$ lines each contain one row of the grid as a string of $N$ characters. U marks an umbrella, S marks your current position, E marks the safe zone, and . marks an empty cell. There is exactly one S and exactly one E.

Output

Print the minimum number of moves needed to reach the safe zone. If you cannot reach the safe zone, print -1.

Constraints

$4 \le N \le 500$

$0 \le K \le 10$

$1 \le H \le 10,000$

$1 \le D \le 5,000$

All given numbers are integers.

Examples3

Example 1
Input
```
4 10 4
S..U
....
....
...E
```
Expected output
```
6
```
Example 2
Input
```
4 2 6
S..U
....
....
...E
```
Expected output
```
-1
```
Example 3
Input
```
4 3 3
S..U
....
....
...E
```
Expected output
```
6
```