Background

Description

给定一个具有n层的数字三角形，从顶至底有多条路径，每一步可沿着左斜或右斜向下走，路径所经过的数字之和为路径的花费，请求出最少路径的花费(如：2-6-8-6 花费22) 输入： 4 2 6 2 1 8 4 1 5 6 8

输出： 10 8 12 2 13 10 1 5 6 8 10

Format

Input

Output

Samples

4
2
6 2
1 8 4
1 5 6 8

10
8 12
2 13 10
1 5 6 8
10

Limitation

1s, 1024KiB for each test case.