After every competition day at JBOI 2012, the contestants, team leaders and organizers can go to the beach and enjoy various activities. Darko is one of the organizers of JBOI 2012 and his job is to bring drinks to the beach.

To bring drinks as quickly as possible, Darko is asking for your help to determine the best route he can take from Hotel Pela to the beach, while visiting all locations that contain drink packages. On a rectangular board with R rows and C columns, the starting position, locations that contain drink packages and the beach can be represented as shown below:

####.##.#.# #S..#.D#.#. .#.....#... .D......B.# ....D...###

The starting location is marked with 'S', the beach is marked with 'B' and the locations of drink packages are marked with 'D'. Darko can step on any location that is not a fence (fences are marked with '#').

Write a program that will calculate and output the minimum number of steps in order for Darko to go from the starting position to the beach after visiting all locations with drink packages. In each step Darko can go to a position which is adjacent to his current position either vertically or horizontally. Darko cannot visit a position that is not shown on the map: in other words, he cannot exit the map - even if there is no fence on the map edges.

Input

The first line of input contains two integers R and C (5 ≤ R, C ≤ 100) - R is the number of rows on the map, and C is the number of columns.

Each of the following R lines contains C characters Mij ('.', '#', 'S', 'D' or 'B'). These characters represent the structure of the map. There will be exactly one 'S' character, exactly one 'B' character and at most three drink packages ('D' characters in the map). There will be at least one drink package.

In test cases worth at least 30% of the full score, there will be exactly one drink package.
In test cases worth at least 30% of the full score, there will be exactly two drink packages.

Output

Your program should output exactly one integer - the required minimum number of steps. If taking all the drinks and going to the beach is impossible, output -1.

Constraints

Time limit: 1 second
Memory limit: 64 megabytes

Examples

input
5 6
#S.###
#...##
.#..##
D..B#.
##.#..

output
9

input
5 6
#S.###
#...##
D#..##
DB...D
##.#.#

output
15