Triangle Minimum Path Sum

Triangle Minimum Path Sum

Given a triangle array, find the minimum path sum from top to bottom.

Input format

The first line contains N. The next N lines contain the triangle (line i has i+1 space-separated ints).

Output format

Print the minimum path sum from top to bottom.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

5
19
28 17
10 3 26
6 48 26 39
48 16 26 34 1

79

9
10
5 31
45 44 13
3 6 39 5
6 31 47 29 0
24 13 8 22 15 45
0 44 14 12 18 49 33
15 24 5 20 11 3 34 31
10 10 13 23 40 23 36 38 33

114