问题 1007. -- 娱乐活动

1007: 娱乐活动

时间限制: 1 Sec  内存限制: 128 MB
提交: 58  解决: 24
[提交][状态][讨论版]

题目描述

ACM协会不仅是一帮拥有严谨思维的“爱码士”,还是一个娱乐活动丰富的社团。最近他们在玩一个这样的游戏。在地上摆一个倒立数字直角等腰三角形,如下图

1

3 2

4 10 1

4 3 2 20

每个会员从第一行第一个格子开始走,他们只能为下或者往右下走,直到走到最后一行。途中经过的数字之和最大的人胜出。于是聪明的“爱码士”就开始想用代码来解决这个游戏(原谅程序猿的思维,每次都把这种游戏用计算机“作弊”)。你的任务是计算最大和为多少。


输入

输入包含多组数据,第一行为测试数据T组(1<=T<=10;以下每组数据的第一行为数字三角形直角边长度L(1<L<=30)(每个数字长度为1)。接下来的L行为数字三角形,每个数都小于231


输出

对于每组数据,输出途中经过数字的最大和s(s<263)


样例输入

1
4
1
3 2
4 10 1
4 3 2 20

样例输出

Case 1: 24

提示

来源

[提交][状态]