# Mountain Ski

One of the ski resorts in Italy hosts a ski slope competition. Each competitor will have to slide down the mountain on skis. At any stage of the descent, the participant receives a certain number of points. After passing the track, the points are added up. The competitor with the most points wins.

The mountain is a triangle, built from integers, equal to points for passing the stage. At each level, a competitor has a choice — to move down left or down right. The beginning of the descent is at the highest point of the mountain, the end is at one of the lowest.

   1
  4 3
 5 6 7
8 9 0 9

Find the maximum total score for the competitor.

## Input format

The first line of input contains one integer $n$ — the number of stages ($1 \le n \le 100$), then $n$ lines follow. Each line describes one “slice” of the mountain and contains exactly $i$ integers $a_1, a_2, \ldots, a_i$ ($-100 \le a_k \le 100, 1 \le k \le i$) — the score for each place.

## Output format

Print one integer — the answer to the problem.

## Sample

### Input

4
1
4 3
5 6 7
8 9 0 9

### Output

20