#1: Bowling (largest path sum in a pyramid of numbers)

You have a pyramid or a triangle of numbers like this one. Starting from the top, walking down, going one step to the adjacent number either to right or to the left until you’ve reached the bottom row. Your task is to write a program to find the largest possible sum considering the conditions above. 

3
7 4
2 4 6
8 5 9 3

In this case, the largest sum is 3 + 7 + 4 + 9 = 23.

NOTICE: The program should be written so it can calculate the largest possible sum maximum within 1 second even with a triangle that consists of 100 rows.

-- Example I:

input:

4 // is the number of rows in the triangle

3
7 4
2 4 6
8 5 9 3

output: 

23

-- Example II:

Input:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Output: 30