★实验任务

正如你所知道的 s_sin 是一个贪玩的不得了的小 P 孩 QAQ，你也知道他最近很喜欢玩一

个叫做太阳帝国的原罪的策略游戏去年他已经和疯狂的 AI 交战了整整一年。而现在，战斗

的序幕又要拉开了。

在某个星球上，该星球由 n*m 个方格组成，每个方格中可能为 boss，s_sin，障碍，道

路，小怪。s_sin 想要去打爆 boss，假设他可以秒杀 boss，现在他的任务只需要到达 boss

所在的位置。如果 s_sin 想要到达某个方格，但方格中有小怪，那么必须打死小怪，才能到

达这个方格。假设 s_sin 只能向上、下、左、右移动一个格子，移动一步用时 1 个时间单位，

*小怪也用 1 个时间单位。假设 s_sin 很强壮，可以*所有小怪。

试计算 s_sin 到达 boss 位置至少需要多少时间。注意：障碍时不能通过的。

★数据输入

输入第一行为两个正整数 n，m (1 < =n，m< =100)， 表示该地图有 n 行 m 列。

接下来 n 行，每行 m 个字符：“.”代表道路 ， “a”代表 boss ， “r”代表 s_sin ，

“#”代表障碍，“x”代表小怪。-The experimental task

As you know s_sin is a fun not the small child P QAQ, you know he loves playing with a recently

A strategy game called the sins of a Solar Empire last year and he has mad at AI for a whole year. And now, the battle

Prelude to open.

On a planet, the planet by n*m squares which, as boss, s_sin, obstacle each square, road

The road, small strange. S_sin wants to hook boss, assuming he can Seckill boss, his task now only need to reach boss

Location. If s_sin wants to reach a square box, but have a little strange, so must kill mobs, to

Reach a square. Assume that s_sin only to the upper and lower, left, right movement of a lattice, move in 1 time units,

Kill mobs in 1 time units. Assume that s_sin is very strong, can kill all the mobs.

Calculate the s_sin arrives at the boss position at least how much time. Note: barrier to adoption.

Data input

The first input two positive integers n, m (=n < 1, m< =100), said the map with n M.

The next N lines, M char