长征漫漫

19XX年，红军某方面军决定奇袭敌军营地，敌军营地排布呈三角状分层排布，每一层之间不相连，每个战点有两条路线，可以走到下一层的两个战点，且第i层共有i个营地。红军需要从三角的上顶点开始出发，沿着营地的路线向下进攻，进攻到最底层的任意一个营地即视为胜利。但是每个营地的人员配布不同，如果红军攻打第i层的第j个战点，则会损失aij名士兵。
现在，请你找到一条路线，使得红军在损失人员最少的情况下获得胜利，并求出最小的损失士兵数。

输入数据有多组，
每一组第一行有n个整数$n(1\le n\le 1000)$，表示战点的层数。
接下来$n$行中，第$i+1$行有$i$个整数，表示第$i$层的$i$个战点权值aij(0≤aij≤1000)
输入以$n=0$结束
保证所有的$n$之和不超过1000。

输出数据共一行，表示最小的代价数

4
2
3 4
6 5 7
4 1 8 3

11

acmer-yez