A maintenance cart must travel across a service floor from the top-left cell (0, 0) to the bottom-right cell (rows-1, cols-1). The floor is a grid where each cell either costs a fixed amount of fuel to enter, or is impassable. Normally the cart may only move one cell right or one cell down at a time, paying the fuel cost of the cell it enters (including the starting cell). As a special allowance, the cart is permitted to use at most one diagonal shortcut during the entire trip: a single move from a cell (r, c) directly to (r+1, c+1), paying only the fuel cost of (r+1, c+1) (no cost is paid for skipping the intermediate cell). The cart may choose not to use the shortcut at all.

Find the minimum total fuel cost to travel from (0, 0) to (rows-1, cols-1).

Input format

Line 1: two integers rows and cols. Each of the next rows lines: cols space-separated integers. A value of -1 means the cell is impassable (can never be entered, by any kind of move); any other value v (0 <= v <= 999) means the cell costs v fuel to enter.

Output format

Print a single integer: the minimum total fuel cost of a route from (0, 0) to (rows-1, cols-1) using right moves, down moves, and at most one diagonal (down-right) move. If (0, 0) or (rows-1, cols-1) is impassable, or no route exists, print -1.

Constraints

• 1 <= rows, cols <= 30
• Each grid value is -1 or an integer in [0, 999]

2 2
0 9
9 0

0

1 3
2 5 1

8