A triangle has r rows; row i (counting from 1) contains exactly i integers. You start on the single number in row 1. From a number at position j in a row you step down to either position j or position j+1 in the next row. Continue until you reach the bottom row.
Return the minimum possible sum of the numbers visited along such a top-to-bottom path.
Input format
Line 1: an integer r, the number of rows.
Next r lines: line i contains i space-separated integers.
Output format
A single integer: the minimum path sum (it may be negative).
Constraints
- 1 <= r <= 300
- -1000 <= each number <= 1000