Description

一个高度为N的数塔由正整数数字三角形组成，即每往下一层，数字台阶多两个。从上走到下，每次只能走到下一层相邻的左，中，右三个台阶。例如，对于三角形：

5

984

56369

1837285

第二层的台阶4，只能走到下层的3，6，9台阶，不能走到5和6台阶。

数塔从上到下，一直到底层，走过便做数字累加，那么，所有可能路径中的数字和最大值是多少呢？例如，上例中的最大值是：5+9+6+8 = 28。

Input

若干数塔，每个数塔由一个整数n（n<=30）开始，后跟n行数字串，表示高为n的数塔。显然数字串每行以两个字符递增。

Output

对应每个数塔，以一行的格式输出路径最大值。

Sample

Input

2
3
235
4
5
984
56369
1837285

Output

8
28

Source: qn