You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Description

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

Format

Input

Output

Samples

4
2
6 2
1 8 4
1 5 6 8

10

Limitation

1s, 1024KiB for each test case.