672. Triangle A

0

Medium

Given a triangle array, find the minimum path sum from the top to the bottom.
At each step, you can move to an adjacent number in the row below.
In other words, if you are at index `i` on the current row, you can move to either index `i` or index `i + 1` on the next row.

Input Format

The first line contains an integer n (number of rows).
The next n lines contain integer arrays representing the triangle.

Output Format

Print the minimum path sum from top to bottom.

Example

Input

4
2
3 4
6 5 7
4 1 8 3

Output

11

Constraints

1 <= n <= 200

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

-10

triangle[0].length == 1

triangle[i].length == triangle[i - 1].length + 1

-10

^{4}<= triangle[i][j] <= 10^{4}Loading...

View Submissions

Console