3028 - 小俞同学的游戏

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

一天,小俞同学突然之间就很没意思,于是她找来了你来玩游戏。她拿来了一堆卡片,把上面都写上了数字,并且把它们分成n摞。游戏的规则是这样的,你俩只可以从一摞牌的上面取一张或者是下面取一张(她想取上面的,于是你只好取下面的了)。

轮流取牌,你们也可以取不同的一摞的牌,只要遵守上面的规则即可。由于规则是她想出来的,所以,也是她先取牌。你俩都非常的聪明,都能用最优的策略来玩游戏,现在由你来算出最后的得分。

题目输入

第一行一个整数n(1<=n<=100).

第二行的第一个整数m代表每一摞有多少张牌(1<=m<=100),接下来m个整数Ci,代表第i张上面的分数(1<=Ci<=1000)

题目输出

一行两个整数p和q,代表小俞同学的得分和你的得分。

输入/输出样例

输入格式

2
1 100
2 1 10
1
9 2 8 6 5 9 4 7 1 3
3
3 1 3 2
3 5 4 6
2 8 7
3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000

输出格式

101 10
30 15
18 18
7000 7000