Moving

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.

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.

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