Gecko

During the rainy season one of the walls in the house is covered with mosquitoes. The wall is tiled with $h \times w$ square tiles: $h$ rows of tiles from top to bottom and $w$ columns from left to right. Between $1$ and $1000$ mosquitoes rest on each tile.

A gecko wants to eat as many mosquitoes as it can under the following rules. It starts by choosing any tile in the top row and eats the mosquitoes on that tile. Then it moves to a tile in the next row down, eats the mosquitoes there, and keeps going the same way until it reaches the floor. When it moves down one row, it may only go straight down, diagonally down to the left, or diagonally down to the right (see Figure 1).

Figure 1 When it moves down one row, the gecko may only go straight down, diagonally down to the left, or diagonally down to the right.

You are given $h$, $w$, and the number of mosquitoes on every tile. Write a program that computes the largest number of mosquitoes the gecko can eat on one trip from the top of the wall to the bottom.

The first line contains two integers. The first integer $h$ ($1 \le h \le 500$) is the number of tile rows on the wall, and the second integer $w$ ($1 \le w \le 500$) is the number of tile columns.

Then $h$ lines follow. The $i$-th line gives the number of mosquitoes on each tile of the $i$-th row from the top. Each line holds $w$ integers separated by a single space, and each integer $m$ ($1 \le m \le 1000$) is the number of mosquitoes on that tile.

Print a single integer, the largest number of mosquitoes the gecko can eat on one trip from the top of the wall to the bottom.