算法分析与设计习题 (参考)

F. 数塔

单点时限: 2.0 sec

内存限制: 256 MB

有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的数字和最小。

9

12 15

10 6 8

2 18 9 5

19 7 10 4 16

输入格式

输入数据首先包括一个整数 C,表示测试实例的个数,每个测试实例的第一行是一个整数 N(1 <= N <= 100),表示数塔的高度,接下来用 N 行数字表示数塔,其中第 i 行有个 i 个整数,且所有的整数均在区间 [0,99] 内。

输出格式

对于每个测试实例,输出路径上的数字和最小值。

样例

Input
1
5
7
3  8
8  1  0
2  7  4  4
4  5  2  6  5
这个题目的数据只是为了方便大家看,读入的时候不需考虑多余的空格和换行
Output
17