Maximum Sum basic

A rectangular table of size $n$ rows by $m$ columns is given. Each cell of this table contains one integer. You can traverse the table from top to bottom, starting from any cell in the top row, and at each step, move to one of the "lower neighboring" cells. In other words, from a cell with coordinates $(i,j)$, you can move to $(i+1,j-1)$, $(i+1,j)$, or $(i+1,j+1)$. If $j=m$, the last of the three movement options is not possible. If $j=1$, the first option is not possible. The route ends in one of the cells of the bottom row.

Write a program that finds the maximum possible sum of values of cells passed along any valid path.

Input

The first line contains $n$ and $m(1\le n,m\le 200)$ — the number of rows and columns. Each of the next $n$ lines contains $m$ integers (with absolute values not exceeding $10^6$) — the values of the cells in the table.

Output

Print one single integer — the maximum possible sum.

Examples