# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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.

First line contains two integers, n - the number of rows ( 1 <= n <= 10^{4}) and s -the
number of subways / columns

(1 <= s <= 100).
Next each n lines contain s integers A_{1}
, A_{2}
,…A_{s}
(-10^{4}
<= A_{i} <=10^{4}
), the number of
coins on each cell. A_{i}
< 0 indicates an obstacle.

Print the maximum number of coins Jake can collect.

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 |