Есептің шарты

Сәнді ұнататын Битаро жаңа кілем сатып алды. Кілем тігінен $H$ жолға және көлденеңінен $W$ бағанға торкөз түрінде бөлінген тіктөртбұрыш пішінді, әрі әрбір торкөз ақ немесе қара түстің біріне боялған. Кілемнің жоғарыдан санағанда $i$-ші жолында, солдан санағанда $j$-ші бағанында ($1 \le i \le H$, $1 \le j \le W$) орналасқан торкөздің түсі $S_i$ жолының $j$-ші таңбасы . болғанда ақ, ал # болғанда қара болады.

Битаро кілемнің ең сол жақ жоғарғы торкөзіне тас қойып, келесі амалды бірнеше рет орындау арқылы сол тасты кілемнің ең оң жақ төменгі торкөзіне жеткізу ойынын ойлап тапты:

• Тас тұрған торкөзден түсі өзгеше әрі оған жоғары, төмен, сол немесе оң жағынан көршілес $1$ торкөзді таңдап, тасты сол торкөзге жылжыту.

Битаро межелі жерге жеткенге дейінгі амалдар санын мүмкіндігінше азайтқысы келеді. Алайда кілемнің өрнегіне байланысты оған жеткізу мүмкін болмауы да ықтимал.

Кілем өрнегі туралы ақпарат берілген кезде, амалды қайталау арқылы тасты сол жақ жоғарғы торкөзден оң жақ төменгі торкөзге жеткізу мүмкін бе екенін анықтайтын, ал мүмкін болса, амалдар санының ең аз мәнін табатын программа жазыңыз.

Шектеулер

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ — ұзындығы $W$ болатын жол ($1 \le i \le H$).
• $S_i$ жолының әр таңбасы . немесе # ($1 \le i \le H$).
• $H, W$ — бүтін сандар.

Ішкі есептер

1. ($4$ ұпай) $H = 1$.
2. ($14$ ұпай) $H \le 5$, $W \le 5$.
3. ($24$ ұпай) $H \le 30$, $W \le 30$.
4. ($58$ ұпай) Қосымша шектеулер жоқ.

Кіріс деректер

Кіріс деректер стандартты кірістен келесі форматта беріледі:

H W
S_1
S_2
:
S_H

Шығыс деректер

Егер амалды қайталау арқылы тасты сол жақ жоғарғы торкөзден оң жақ төменгі торкөзге жеткізу мүмкін болса, амалдар санының ең аз мәнін, ал мүмкін болмаса -1 мәнін стандартты шығысқа $1$ жолда шығарыңыз.

Мысалдар

Кіріс мысалы 1

4 5
...#.
#####
...#.
#.###

Шығыс мысалы 1

9

Мысалы, суреттегідей амалдарды қарастыруға болады.

Сол жақтағы мысалда $9$ амалмен, ал оң жақтағы мысалда $13$ амалмен тасты сол жақ жоғарғы торкөзден оң жақ төменгі торкөзге жеткізуге болады.

$9$ реттен аз амал санымен жеткізу мүмкін болмағандықтан, $9$ шығарылады.

Бұл кіріс мысалы $2, 3, 4$-ші ішкі есептердің шектеулерін қанағаттандырады.

Кіріс мысалы 2

3 3
...
...
...

Шығыс мысалы 2

-1

Басынан-ақ ешқандай амал жасай алмайтын жағдайлар да болады. Бұл жағдайда тасты оң жақ төменгі торкөзге жеткізу мүмкін емес болғандықтан, -1 шығарылады.

Бұл кіріс мысалы $2, 3, 4$-ші ішкі есептердің шектеулерін қанағаттандырады.

Кіріс мысалы 3

1 5
.#.#.

Шығыс мысалы 3

4

Бұл кіріс мысалы барлық ішкі есептердің шектеулерін қанағаттандырады.

Кіріс мысалы 4

5 5
###.#
.#...
.#..#
.####
##..#

Шығыс мысалы 4

12

Бұл кіріс мысалы $2, 3, 4$-ші ішкі есептердің шектеулерін қанағаттандырады.

Кіріс мысалы 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Шығыс мысалы 5

12

Бұл кіріс мысалы $3, 4$-ші ішкі есептердің шектеулерін қанағаттандырады.