如图所示，有一个层数为n（n≤1000）的数字三角形。现有一只蚂蚁从顶层开始向下走，每走下一级时，可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。

第一个整数为n，以下n行为各层的数字。

一个整数，即最大值，保证不超过整型的最大范围。

5
1
6 3
8 2 6
2 1 6 5
3 2 4 7 6

23