Subway Surfers

Jake is a character of a well-known game named Subway Surfers. He is being
chased by police because of drawing illegal graffiti. So, he starts to run, avoiding
obstacles on the path. There are multiple subways on the road and coins lying on
them. As jake runs, he collects as many coins as possible.
There are n rows and s subways. Jake can move to the left, right or the same
subway of the next row. He dies if he crashes with any obstacle. Jake can start
running from any subway of the first row.

Determine the maximum number of coins Jake can collect before he reaches the
end of the path or dies.

Input

First line contains two integers, n - the number of rows ( 1 <= n <= 104) and s -the
number of subways / columns
(1 <= s <= 100).
Next each n lines contain s integers A1
, A2
,...As
(-104
<= Ai <=104
), the number of
coins on each cell. Ai
< 0 indicates an obstacle.

Output

Print the maximum number of coins Jake can collect.

Samples

Input	Output
5 3 1 4 2 6 2 -1 -4 1 10 2 5 1 3 4 4	25

Input	Output
4 4 3 4 1 9 6 2 2 1 5 -5 3 7 2 12 4 1	27