Background

Special for beginners, ^_^

Description

设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示：

若要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。

Format

Input

第一行为 $n(n<10)$，表示数塔的层数。

从第 $2$ 行至 $n+1$ 行，每行有若干个数据，表示数塔中的数值。

Output

输出路径和最大的路径值。

Samples

5
13
11  8
12  7  26
6  14  15  8
12  7  13  24  11

86

Limitation

1s, 1024KiB for each test case.