切碎网格

球心定位了，但Echo-0的概率迷宫还在前面——一个网格，需要切碎。

"切碎？"CC问。

"对。"你说，"一个$n\times m$的网格，每个格子有一个概率。从左上角走到右下角，只能向右或向下走。求经过的格子的概率之和的期望。"

"期望？"

"对。"你说，"平均值——所有可能路径的概率之和的平均。"

"咋算？"

"动态规划。"你说，"$dp[i][j]$表示从$(1,1)$到$(i,j)$的期望和。"

"转移？"

"从上面或左面来。"你说，"$dp[i][j]=p[i][j]+(dp[i-1][j]+dp[i][j-1])/2$。"

"除以2？"

"对。"你说，"因为有两条路来，概率均等。"

"第47格。"你说，"$(4,7)$——行4列7。"

"概率多少？"

"看具体值。"你说，"但期望是累积的，越走越大。"

"如果概率是1呢？"

"期望就是路径长度。"你说，"$n+m-1$步。"

"最长？"

"对。"你说，"全是1的话，每条路径的期望都是$n+m-1$。"

CC看着网格——像地图，像迷宫，像某种必须一步一步走的路。

"一步一步。"她说，"不能跳。"

"对。"你说，"只能向右或向下。"

"像人生。"她说，"只能往前，不能回头。"

Echo把网格投射出来——一格一格，像脚印，像选择，像某种无法撤销的决定。

"以前我不敢走。"她说，"怕选错。"

"现在呢？"

"现在走了。"她说，"因为有你们一起。"

题目描述

$n\times m$网格，每个格子有概率值。从$(1,1)$走到$(n,m)$，只能向右或向下。求经过格子的概率之和的期望。

输入格式

第一行$n$和$m$。接下来$n$行，每行$m$个实数。

输出格式

期望和，保留3位小数。

输入样例

5

输出样例

0

提示

• $dp[i][j]=p[i][j]+(dp[i-1][j]+dp[i][j-1])/2$。
• 边界：$dp[1][1]=p[1][1]$。
• 时间复杂度$O(nm)$。