Током истраживања старог храма, Милош је нашао мистичну шаховску таблу која има \(h\) редова и \(w\) колона на којој су нека од поља блокирана уз помоћ магије. Он је постао опседнут овом таблом и кренуо да игра веома необичну игру на њој.

На табли се увек налази тачно једна фигура коју Милош у току игре може да замењује другим фигурама. На почетку игре то је краљ који се налази на горњем левом пољу, \((1,1)\). Фигуре се померају по уобичајеним правилима шаха, међутим није могуће ставити их на блокирана поља. За свако померање фигуре Милошу треба 1 секунд. Његов циљ је да што пре стави неку фигуру на доње десно поље, \((h,w)\).

У произвољном моменту Милош може да замени тренутну фигуру неком другом фигуром на истој тој позицији. Међутим, он не може ово да уради тренутно, него му за то треба одређено време, у зависности од тога коју нову фигуру почиње да користи.

Краљ : Милошу треба 1 секунд да замени било коју фигуру краљем.
Краљ се у једном потезу може померити на једно од 8 суседних поља ако то поље није блокирано.




Ловац: Милошу треба 2 секунде да замени било коју фигуру ловцем.
Ловац се у једном потезу може померити дијагонално произвољан број поља, све док ни једно од поља на његовом путу није блокирано.



Топ: Милошу треба 3 секунде да замени било коју фигуру топом.
Топ се у једном потезу може померити лево, десно, горе или доле произвољан број поља, све док ни једно од поља на његовом путу није блокирано.



Коњ: Милошу треба 4 секунде да замени било коју фигуру коњем.
Коњ се у једном потезу може померити 2 поља у произвољном од четири смера (горе, доле, лево, десно) и 1 поље у једном од два смера ортогонална на претходни смер. Није битно да ли су поља преко којих коњ успут прелази блокирана или не.


Краљица: Милошу треба 5 секунди да замени било коју фигуру краљицом.
Краљица, у једном потезу, може да се помери лево, десно, горе, доле или дијагонално произвољан број поља, све док ни једно од поља на њеном путу није блокирано.


Помозите Милошу и реците му за колико најмање секунди може да заврши ову игру, или му саопштите да то није могуће.

Опис улаза

У првој линији стандардног улаза налазе се два природна броја \(h\) и \(w\), који обележавају редом висину и ширину табле. У наредних \(h\) редова се налази низ дужине \(w\) који се састоји само од карактера . и #, где . означава да је поље слободно, а # да је поље блокирано.

Опис излаза

На излаз исписати цео број \(t\), најмањи број секунди да Милош постави фигуру на поље \((h,w)\), односно \(-1\) ако то није могуће.

Пример 1

Улаз

3 3
...
.#.
...

Излаз

3

Пример 2

Улаз

3 5
.####
##.##
####.

Излаз

6

Пример 3

Улаз

10 10
...#.###..
.....#####
...##..#.#
#....#....
.#.......#
##..#.....
......#...
..##..#.#.
..#..#..#.
..#..##...

Излаз

8

Објашњење примера

Пример 1:

Пример 2:

Пример 3:

Ограничења

• \(1 \leq h,w \leq 500\)

Тест примери су подељени у 5 дисјунктних група:

• У тест примерима вредним \(10\) поена: \(h,w \leq 5\).
• У тест примерима вредним \(10\) поена: \(h,w \leq 200\) и ако постоји решење, постоји и оптимално решење које не захтева замену фигура.
• У тест примерима вредним \(40\) поена: \(h,w \leq 200\).
• У тест примерима вредним \(10\) поена: Ако постоји решење, постоји и оптимално решење које не захтева замену фигура.
• У тест примерима вредним \(30\) поена: Без додатних ограничења.