There is a number tower which consists of many positive integers, and it looks like a triangle as below :
1
4 6
6 9 3
6 3 7 1
2 6 3 1 8
The first layer contains one positive integer, and the second one contains two, and so on.
Our goal is to find a path from top to bottom which has the largest sum in all paths. The path starts from the root node (the first number in the first layer), and each node can only choose one of the nearest two descendant nodes to move to. For example, 4 in the second layer can only move to 6 or 9 in the third layer. Please, sum up all the number in the path and print the largest sum.
The first line is a positive integer n, that represents the height of the tower. (n <= 10) Each line in next n lines contains m positive integers whose value are not greater than 9 in the mth layer, and all number is seperated by white spaces.
Print the largest value in all paths, and remenber to print a new line in the end of the anwser.