Hamster

Time limit2sMemory limit1024 MB

Summary

Find the largest total of larvae on a path from the northwest to the southeast corner of an N by M grid that never revisits a cell.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix, Implementation
Solved: No attempts yet

Problem

The hamster lives in a rectangular enclosure. The floor is divided into square fields of the same size, forming a grid, and each field holds several larvae.

The hamster starts in the northwest corner. On each visited field he collects the larvae into his bowl, places a trap on the field, and moves to a neighboring field that shares a side with the one he is leaving. He cannot return to a field he has already visited, since he would be caught in one of his own traps. His journey ends in the southeast corner.

Given the number of larvae in each field, find the maximum number of larvae the hamster can collect on a journey that avoids all traps.

Input

The first line contains two integers $N$ and $M$ ( $2 \le N, M \le 1000$ ), the number of rows and columns in the grid. Then $N$ lines follow, each containing $M$ integers, the number of larvae in each field. Each line is one row of the grid. The first number of the first line is the northwest corner, and the last number of the last line is the southeast corner.

The number of larvae in any field is between $0$ and $1000$ , inclusive.

Output

Output a single number: the maximum number of larvae the hamster can collect.

Examples2

Example 1
Input
```
2 2
1 2
3 4
```
Expected output
```
8
```
Example 2
Input
```
3 4
2 2 4 0
1 3 1 0
2 5 3 1
```
Expected output
```
24
```