Moving

Interview

Time limit1sMemory limit256 MB

Summary

Jungyu collects the most candy possible walking from the top-left room to the bottom-right room with right, down, and diagonal moves.

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

Problem

Jungyu is trapped in a maze of size $N \times M$ . The maze is divided into rooms of size $1 \times 1$ , and every room holds some candy. The top left room is $(1, 1)$ and the bottom right room is $(N, M)$ .

Jungyu is at $(1, 1)$ and wants to reach $(N, M)$ . When he is at $(r, c)$ he can move to $(r+1, c)$ , $(r, c+1)$ , or $(r+1, c+1)$ , and every time he visits a room he can take all of the candy in that room. He cannot leave the maze.

Find the largest number of candies Jungyu can collect on his way to $(N, M)$ . The candy in the starting room $(1, 1)$ counts as well.

Input

The first line contains the size of the maze, $N$ and $M$ . ( $1 \le N, M \le 1000$ )

Each of the next $N$ lines contains $M$ numbers. The $c$ -th number on the $r$ -th line is the number of candies in room $(r, c)$ , which is at least 0 and at most 100.

Output

Print on the first line the largest number of candies Jungyu can collect on his way to $(N, M)$ .

Examples4

Example 1
Input
```
3 4
1 2 3 4
0 0 0 5
9 8 7 6
```
Expected output
```
31
```
Example 2
Input
```
3 3
1 0 0
0 1 0
0 0 1
```
Expected output
```
3
```
Example 3
Input
```
4 3
1 2 3
6 5 4
7 8 9
12 11 10
```
Expected output
```
47
```
Example 4
Input
```
1 1
0
```
Expected output
```
0
```