Trucking Diesel

A diesel truck carries diesel from a start cell to a destination cell. The truck has no separate fuel tank: the cargo diesel is also the fuel. Find the maximum number of liters that can still be on the truck at the destination without running out along the way. If the destination cannot be reached with the starting fuel, print $-1$.

The terrain is an $m$-by-$n$ grid of altitudes in meters. Each altitude is between $0$ and $4000$ and is a multiple of $100$. The first row is the northern edge, the last row is the southern edge, the first column is the western edge, and the last column is the eastern edge. The truck starts at the north-west corner $(0, 0)$ and must reach the south-east corner $(m - 1, n - 1)$. In one step it may move to an adjacent cell to the east, south, or west. It cannot move north or diagonally.

Diesel weighs $1.0$ kg per liter. A downhill or flat step costs $10$ liters. An uphill step costs $10$ liters plus $4$ additional liters for every $100$ m of altitude gain and for every whole ton of total mass at the start of the step, where mass is rounded down to tons in $1000$ kg units. For example, if the mass at the start of a segment is $26010$ kg and the altitude rises from $400$ m to $700$ m, the segment costs $10 + 3 \times 4 \times 26 = 322$ liters.

Before each step the truck may throw away an integer number of liters of diesel. The unladen truck weighs $8$ tons ($8000$ kg) and it starts with $25000$ liters of diesel.

The first line contains $m$ and $n$. Each of the next $m$ lines contains $n$ altitudes. Every altitude is between $0$ and $4000$ and is a multiple of $100$.

Print the maximum number of liters that can be delivered. If the truck can arrive with an empty tank, print $0$. If the destination cannot be reached, print $-1$.