Mecho#292

Mecho

1 second
64 megabytes
Very easy

Mecho the bear has found a little treasure—a secret honeypot full of honey! He was happily enjoying his prize until suddenly, one bee saw him and sounded the alarm. Mecho knows that now, the bees will leave their hives and start spreading around the forest to catch him. He realizes he must leave the honeypot and hurry home, but the honey is so sweet that Mecho does not want to stop eating too early. Help Mecho determine the latest possible moment he can stop eating honey and still manage to get home before being caught by the bees.

The forest is represented as an n \times n square grid. The cells of the grid are parallel to the north-south and east-west directions. Each cell may contain a tree, grass, a hive, or Mecho's home. Two cells are considered adjacent if they share a side (north, south, east, or west; not diagonal). Mecho can only move to adjacent cells. He can only walk on grassy cells and cannot move through trees or hives. Mecho can take at most steps per minute.

As soon as the alarm is sounded, Mecho is at the grassy cell containing the honeypot, and all bees are in every cell containing a hive (there may be multiple hives). From this moment, during each following minute, these events happen in this order:

In other words, when the alarm is sounded, bees only occupy the hive cells. At the end of the first minute, they occupy all grassy cells adjacent to hives (and still the hives themselves). At the end of the second minute, they additionally occupy all grassy cells adjacent to those. This continues until, given enough time, all reachable grassy cells are filled by the bees.

Neither Mecho nor the bees can leave the forest grid. According to the rule, Mecho always eats honey for an integer number of minutes.

The bees catch Mecho if at any point he is in a cell currently occupied by bees.

Write a program that, given a map of the forest, determines the maximum number of minutes Mecho can stay at his initial cell to eat honey and still be able to reach his home before the bees catch him.

Input

The first line contains two integers: the grid size (1 \leq n \leq 800) and the maximum number of steps (1 \leq s \leq 1\,000) Mecho can take in each minute, separated by a space.

The next lines describe the map of the forest. Each line contains characters, representing one row of the grid. Possible characters:

denotes a tree. denotes a grassy cell. denotes Mecho's starting cell and the location of the honeypot, also a grassy cell. denotes Mecho's home, which Mecho can enter but the bees cannot. denotes a hive.

Note: The map contains exactly one letter , exactly one letter , and at least one letter . It is guaranteed there is a sequence of adjacent cells connecting Mecho's start () to his home (), and a sequence of adjacent cells connecting at least one hive to . These sequences may be of length zero (if home or a hive is adjacent to ). Bees cannot spread into or through the home cell (); this cell is like a tree for bees.

Output

Print one integer: the maximum possible number of minutes Mecho can keep eating honey at his starting cell and still safely reach home.

If Mecho cannot possibly reach his home before being caught, print .

Examples

Example 1

Loading
Loading