2063. 冒险岛

【问题描述】

这时，我们的主人公F1（没有什么好名字取，为了简单，暂且这样）来到了一块神秘的地方——冒险岛，这是一个充满荆棘的地方，随时都可能有生命危险。F1也深知这一点，他做好了充分准备，他已经通过高空扫描技术对冒险岛进行了分析。

冒险岛是由N*M个单位方格组成，即N行M列的网格。格子有两种形状：沙漠与圣水湖。每一个沙漠都有一个摧毁值D，当F1走到一个摧毁值为D的沙漠时，他的生命值将减少D，每一个圣水湖都有一个容量C，当F1走到一个容量为C的圣水湖时，他将得到C单位圣水。

主人公F1可以向下（行数增加）向右（列数增加）的移动，他必须从(1,1)走到(n,m)（第N行M列，下同），中间不能走出这个岛。由于某种不为人知的力的作用（外星人？宇宙引力？或是四维空间中的“物质”？谁知道！），使得从(1,1)到(n,m)一定会经过沙漠。你不必担心F1的生命，也许他的生命值有无穷大，也许他凭着坚强的意志可以在生命值为负数的情况下移动——他一定能走出这个岛，在最后走出(n,m)时，他需要用他得到的所有圣水去弥补他失去的生命值，你只需关心他的“精神面貌值”：得到的圣水与失去的生命值的比值。你需要使“精神面貌值”最大。

【输入说明】

第一行有两个整数N,M（1<=N,M<=300）；接下来N行，有一行有M个整数，第i行有j个整数Pij（-1000000<=Pij<=1000000）描述格子(i,j)。如果小于0，则表示摧毁值为|Pij|的沙漠；否则，表示容量为Pij的圣水湖。

【输出说明】

仅一个数，表示最大“精神面貌值”，精确到小数点后4位。

【样例输入】

3 3

100 -20 -30

-100 -100 -100

-100 100 -100

【样例输出】

0.9091