## CBOJ 2022 Welcome Contest Problem 4 - Highest Weight Path

While transporting muffins down a mountain

tripped and sent his muffins tumbling down.needs to get his muffins back, but can't travel up the mountain due to spinal issues from carrying CBOJ. can see where the muffins are and needs your help to find the optimal path to maximize the number of muffins while always moving diagonally down to the left or diagonally down to the right. His parents are about to ask how many muffins he's bringing and he can't afford to be wrong!

#### Input Specification

The first line will contain a single positive integer \(1 \le N \le 10^3\).

The following \(N\) lines each contain a row of positive integers, with the \(i\)th line containing \(i\) integers, the number of muffins at each location. It can be assumed that the values are nonnegative and do not exceed \(10^9\).

#### Output Specification

Provide a single integer, the maximum number of muffins that Zeyu can get.

#### Subtasks

##### Subtask 1 [50%]

\(1 \le N \le 10\)

##### Subtask 2 [50%]

No additional constraints.

#### Sample Input:

```
5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 8
```

#### Sample Output

`13`

#### Sample Explanation

```
1
/
1 1
\
1 2 1
/
1 3 3 1
\
1 4 6 4 8
```

\(1+1+2+3+6 = 13\)

Note that it is impossible for Zeyu to get the \(8\) muffins at the bottom right because he would miss out on too many muffins on the left side.

## Comments