F. 推箱子
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小银在一个 n × m 的地图上玩推箱子游戏。地图上可能会有一些障碍，其他位置都是空地。小银和箱子开始时所在的位置以及目标点均是空地。

推箱子的规则如下：小银每步只能向上、向下、向左或向右移动一格。如果目标位置是障碍，或者超出了边界，那么不能这样移动。如果目标位置是箱子，那么箱子会向同一方向移动一格。如果箱子移动到的位置是障碍、箱子或者超出了边界，那么也不可以这样移动（不能同时推动多个箱子，箱子也不能占据同一个格子）。箱子到达目标点后不会消失且可以推离目标点。

幸运的是，地图中永远都只有两个箱子和两个目标点，请你求出将所有箱子推至目标点所需的最少步数，如果无解则输出 -1。

Input

第一行两个整数 n, m (1 ≤ n, m ≤ 15)，代表地图的行列。

接下来 n 行，每行输入一个长度为 m 的字符串，其中 "." 表示空地，"*" 表示障碍物，"#" 表示箱子，"@" 表示目标点，"s" 表示人。

保证数据中箱子数与接收点数均为 2，且人、箱子、目标点这五个点互不重合。

Output

输出一行一个整数，表示最少步数。如果无解则输出 -1。

Examples
Input
7 7
.....*@
.....*.
.#**...
..**...
...s...
.....#.
......@
Output
26
Input
4 4
##@@
s...
....
....
Output
-1
Note

样例一中人的最优移动路线如下：

人一共移动了 26 步，其中  →  代表直线移动。

样例二显然无解。