# Practice on Toph

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

# Subway Surfers

By · Limits 1s, 512 MB

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

InputOutput
```5 3
1 4 2
6 2 -1
-4 1 10
2 5 1
3 4 4
```
```25
```
InputOutput
```4 4
3 4 1 9
6 2 2 1
5 -5 3 7
2 12 4 1
```
```27
```

### Statistics

NaN% Solution Ratio