Pretende-se calcular a maior soma possível movendo-se a partir do topo de um triângulo até ao nível mais baixo, movendo-se sempre por valores adjacentes na linha seguinte.

No triângulo seguinte, a maior soma possível é 25, que corresponde a começar no topo (3), mover para 7, 4 e por fim, 11.

3

7 4

2 4 6

7 4 11 3

O input é constituído por uma linha com um número N seguido de N linhas com os números da linha correspondente separados por espaços. O triângulo do exemplo anterior seria passado como:

4

3

7 4

2 4 6

7 4 11 3

O output do programa deverá ser uma única linha com a maior soma possível. Neste caso, seria uma única linha com o número 25.