The Hero is on the way to beat the Devil, now he comes near to a waterfall flow.
The Devil puts a magic on the waterfall flow in order to stop the Hero.

The magic makes the waterfall flow come into being m * n (m lows and n columns) blocks, each block is bound with a number Hi, it means that if the Hero comes into that block, he will be injured by Hi HP.

Now, the Hero wants to kill the Devil, he must go from the foot of the waterfall flow to the top of it. The Hero can choose one of n foot blocks to selected as the starting point, and he can only go upward and towards the left, as well as the right.

To kill the Devil, he must left more and more HP, can you help him?

Input until EOF.
Each test will contain two integers m and n (3 <= m, n <= 20), and a m * n matrix. The matrix includes m * n integers Hi (1 <= Hi <= 1000).

A line includes a integer with the injured HP.