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

P. 扑克牌游戏

单点时限: 2.0 sec

内存限制: 256 MB

Fox 和 Online 两人玩扑克牌游戏,现在桌面上有 n 堆牌,每张牌上都有数字。

Fox 先抽牌,他可以抽任意一堆牌的最上面一张,Online 后抽,Online 可以抽任意一堆牌的最下面一张。两人轮流抽牌,直到牌全部抽完。

Fox 和 Online 都很聪明,他们都想让自己最后手上的牌的数字总和尽可能大。

输入格式

第 1 行:一个整数 () 为问题数。

接下来 T 组测试数据,每组测试数据按如下格式输入:

第一行输入一个正整数 n(1≤n≤100),表示牌的堆数;

接下来有 n 行,每行表示一堆牌,每行的第一个数 Si(1≤Si≤100) 表示第 i 堆牌的数目,接下来是 Si 个正整数 c1,c2, …,ck, …,csi(1≤ck≤1000),依次是第 i 堆中从顶部到底部的每张牌上的数字。

输出格式

对于每个问题,输出一行问题的编号(0 开始编号,格式:case #0: 等)。

然后对应每个问题 , 在一行中输出两个数,分别表示 Fox 和 Online 都使用最佳策略进行抽牌,最后手上牌的数字的总和。

样例

Input
3
10
5 1 2 3 4 5
9 12 90 23 8 9 4 5 6 10
3 21 20 19
1 1
10 1 2 3 4 5 6 7 8 9 10
6 6 9 8 3 13 2
7 1 3 5 6 2 8 10
8 10 20 30 40 50 9 8 6
2 90 80
11 9 8 7 6 5 4 3 2 1 10 12
3
3 1 3 2
3 5 4 6
2 8 7
4
10 2 3 4 5 6 7 8 9 10 11
5 10 12 9 7 5
3 19 21 23
7 11 12 13 14 15 16 18
Output
case #0:
458 326
case #1:
18 18
case #2:
127 143