Problem C: Skiing (Easy-15)

Problem C: Skiing (Easy-15)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 453  Solved: 115
[Submit][Status][Web Board]

Description

Yuki is an outgoing girl and she enjoys all the sports, especially snow sports like skiing.

Now she is skiing in a world-famous ski resort — Super Ultra Ski Training Center (SUSTC). The map of SUSTC can be considered as a grid map with \(n\) rows and \(m\) columns. Since the ski facility is uneven, each grid \((i,j)\) has its own height \(h_{i,j}\).

Yuki starts her skiing at the grid \((1,1)\) — the top left grid, and her destination is at the grid \((n,m)\) — the bottom right grid. Each time she can only ski to one of the adjacent grids — the left, the right, the above, or the below grid. Obviously, the minimum distance for Yuki to ski to the destination is \(n+m-2\) if she chooses an arbitrary Manhattan path.

However, with the elevation change during her skiing, Yuki’s speed will also change remarkably. Specifically, suppose that the velocity of Yuki at grid \((x,y)\) is \(v\), then it takes \(\frac1v\) time units for Yuki to move to \((x,y+1)\), and the velocity at grid \((x,y+1)\) will be changed to \(v\cdot 2^{h_{x,y}-h_{x,y+1}}\). Suppose that the initial velocity when Yuki at grid \((1,1)\) is \(v_0=1\), could you please tell Yuki the minimum time for her to arrive at the destination.

Input

The first line contains two integers: \(n\) and \(m\) \((1\leq n,m\leq 300)\) — size of the grid map.

Each of the next \(n\) lines contains \(m\) integers. The \(j\)-th number in the \(i\)-th line denotes \(h_{i,j}\) \((1\leq h_{i,j}\leq 15)\).

Output

Print one line with the value — the minimum time for Yuki to arrive at the destination.

The value should be accurated to exactly 2 decimal places.

Sample Input

2 3
1 2 3
4 5 6

Sample Output

7.00

HINT

[Submit][Status]