Repel

Time limit1sMemory limit256 MB

Summary

Reach the exit from the entrance with the fewest unprotected entries onto wild squares, using Repel squares that shield a fixed number of steps.

Level: Medium6 of 10
Topics: Shortest path, Graph
Solved: No attempts yet

Problem

You have just entered the last dungeon of Victory Road, and your Pokemon are in bad shape. You want to cross the dungeon while meeting wild Pokemon as few times as possible, because the rest of your party may not survive another fight. Some squares of the dungeon apply Repel, a scent that keeps wild Pokemon away for a fixed number of steps.

You may move one square at a time, up, down, left, or right. The rules are as follows.

You start at the entrance with 0 protected steps left.
Each move is one step. If at least 1 protected step is left, the move is protected by Repel and the count of protected steps drops by 1. If no protected step is left, the move is unprotected. An unprotected move into a square where wild Pokemon live counts as one dangerous step.
After the move, if the square you reached is a Repel square of value $v$ and fewer than $v$ protected steps are left, the count of protected steps becomes $v$ . Repel is not additive. The scent is applied only to someone with fewer steps left on the current scent. Stepping on the same Repel square again applies it again.
Wild Pokemon live only on squares marked .. A move into any other square is never counted, even when it is unprotected.

Find the smallest number of dangerous steps needed to walk from the entrance to the exit.

Input

The first line contains two integers $R$ and $C$ ( $1 \le R, C \le 100$ ). Each of the next $R$ lines contains a string of length $C$ describing one row of the dungeon.

X is the entrance, where you start.
Y is the exit.
A character from 1 to 9 or from A to F is a Repel square. Read as a hexadecimal digit, its value is the number of steps the Repel lasts. There are at most 100 Repel squares.
. is a square where wild Pokemon live.
# is a wall, which you cannot enter.

The exit is always reachable from the entrance.

Output

Print, on one line, the smallest number of steps that enter a square where wild Pokemon live while no Repel protects you.

Examples3

Example 1
Input
```
5 5
X#3..
.#...
...#.
.2#..
..#Y.
```
Expected output
```
7
```
Example 2
Input
```
1 6
X....Y
```
Expected output
```
4
```
Example 3
Input
```
3 9
X.......Y
.#######.
F........
```
Expected output
```
1
```