Consider the number triangle shown on the right. Write a program that calculates the smallest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Similar to Pascal Triangle, each step can go either diagonally down to the left or diagonally down to the right.

Question:
Write a program that finds the smallest sum that starts at the top and ends somewhere at the base.

Input specification
The first line contains an integer (n) which represents the number of rows. Then, in the following n lines, you will be given numbers which are between 0 and 1000. The numbers are given such that

• the first line will have one number
• the second line will have two numbers
• : : :
• the nth line will have n numbers

Output specification
A single line containing the smallest sum using the traversal specified.