eolymp
Competitions

Азербайджан - подготовка. Март 16

Nuts for nuts

So as Ryan and Larry decided that their nuts don't really taste so good, they realized that there are some nuts located in certain places of the island, and they love them! Since they're lazy, but greedy, they want to know the shortest tour that they can use to gather every single nut! Can you help them?

Input

The first line of each test case contains the dimensions of rectangular island x and y (x, y20). It is followed by x lines of y characters each as a map of the area, consisting of symbols ".", "#" and "L". Larry and Ryan are currently located in "L". The nuts are represented by "#". The children can travel in all 8 adjacent directions in one step. There will be at most 15 places where there are nuts, and "L" will appear only once on the map.

Output

Print for each test case on a separate line the minimum number of steps to gather all the nuts starting from "L", and returning to "L".

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 5
L....
#....
#....
.....
#....
8 10
L.........
..........
.......#..
..........
#....#....
.........#
..........
....#.....
Output example #1
8
23