# Turtle

There is an $N \times M$ rectangular grid. The turtle is in the leftmost top corner. Each cell of the grid contains a number. The turtle can make moves of three types:
* 1 step down,
* 1 step to the right or
* 1 step to the down-right diagonal direction in a single move.

The turtle finishes the path in the rightmost bottom cell. Let’s calculate the sum of all numbers on visited cells (including the starting and the finishing cells). Find the minimal possible value of this sum.

## Input format
The first line contains two integer positive numbers $N, M (1 \le N, M \le 1,000)$. The following $N$ lines contain the description of the grid. Each of these lines contains $M$ integers — numbers in the grid cells. All those integers are between $−1,000$ and $1,000$, inclusive.

## Output format
Print the only number: the maximal sum of all numbers on a turtle’s path from the leftmost top cell to the rightmost bottom cell.

### Sample 1

#### Input

4 4
1 3 5 2
-1 4 2 9
5 -6 1 -4
-6 6 -2 2

#### Output

-7

### Sample 2

#### Input

2 4
1 2 3 4
5 6 7 8

#### Output

14