AT_arc003_3.[ARC003C] 暗闇帰り道

漆黑归家路

高桥君一个人走夜路从学校回家。

他所居住的城市是一个被分为小格的长方形。高桥君一秒只能向东、南、西、北方向移动一格。

输入给出格子$i,j$的阳光值$c_i,_j$，$t$秒时，该格子的明亮度为$0.99^t×c_i,_j$$（出发时间为$0$秒）。

从学校回到家的路径明亮度为路线所经格子的明亮度的最小值。

高桥君有黑暗恐惧症，会尽可能地选择明亮度大的路径。

请求出他回家路径中的最大明亮度。

第$1$行为空格隔开的$N$,$M$,第$2-N+1$行是一个$N×M$的矩阵。格子的状态用s,g,1-9,#来表示。

第$i$行的第$j$个字母$c_i,_j$ 表示格子$i,j$的状态。

• s 学校的位置。
• g 家的位置。
• 1-9 该格的阳光值。
• # 此路不通。
• 高桥君无法走出城市外。
• s,g唯一且不相邻。

输出的第一行为所求的最大明亮度，若路径不存在则输出-1，答案的相对误差控制在1e-9以内，请在末尾输出换行。

样例1

输入

3 3
s52
743
32g

输出

2.910897

• 時刻0: 从学校$(1,1)$出发。
• 時刻1: 移动到$(2,1) $。时间 $t=1$, 阳光值$=7$ 、$(2,1)$ 的明亮度为$6.93$。
• 時刻2: 移动到$(2,2)$ 。时间 $t=2$, 阳光值$=4$ 、$(2,2)$的明亮度为$3.9204$。
• 時刻3: 移动到$(2,3)$ 。时间 $t=3$, 阳光值$=3$、$(2,3)$的明亮度为$2.910897$。
• 時刻4: 回到家$(3,3)$了 。当前最小的明亮值是时间 $t=3$时的$(2,3)$的明亮度为$2.910897$，答案也就是$2.910897$。
  

样例2

输入

4 6
g31784
621415
627914
7451s3

输出

2.97

不需要解释。