题目描述

贝西和农场主约翰的其他奶牛今年冬天要去滑雪旅行。一天，贝西发现自己位于一个$R$行（$1 \leq R \leq 100$）$C$列（$1 \leq C \leq 100$）的海拔网格$E$的左上角（海拔值$E$的范围是$-25 \leq E \leq 25$）。为了尽快加入约翰和其他奶牛的迪斯科派对，她必须仅通过向北、南、东、西四个方向移动，到达右下角。

贝西的初始速度为$V$（$1 \leq V \leq 1,\!000,\!000$）。她发现自己的速度与海拔变化之间存在一种特殊关系：当从海拔$A$的位置移动到相邻的海拔$B$的位置时，她的速度会乘以$2^{A-B}$。从一个位置移动到相邻位置所需的时间等于她在起始位置时速度的倒数。

请计算贝西到达右下角所需的最短时间，结果保留两位小数。

输入

• 第1行：三个空格分隔的整数$V$、$R$、$C$，分别表示贝西的初始速度、网格的行数和列数。
• 第2到$R+1$行：每行包含$C$个整数，表示网格中对应位置的海拔$E$。

输出

一个精确到两位小数的数值，表示贝西到达右下角的最短时间。

输入数据示例 1

1 3 3  
1 5 3  
6 3 5  
2 4 3  

输出数据示例 1

29.00  

提示

贝西的最优路径为：

• 从$(1,1)$出发，时间$0$，速度$1$
• 向东到$(1,2)$，时间增加$\frac{1}{1}=1$，速度变为$1 \times 2^{1-5}=1/16$
• 向南到$(2,2)$，时间增加$\frac{1}{1/16}=16$（因为起始速度为$1/16$，倒数为$16$），速度变为$1/16 \times 2^{5-3}=1/4$
• 向南到$(3,2)$，时间增加$\frac{1}{1/4}=4$，速度变为$1/4 \times 2^{3-4}=1/8$
• 向东到$(3,3)$，时间增加$\frac{1}{1/8}=8$，总时间$1+16+4+8=29$

来源

USACO 2005年10月黄金组