说明

一天，小俞同学突然之间就很没意思，于是她找来了你来玩游戏。她拿来了一堆卡片，把上面都写上了数字，并且把它们分成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

提示

在第一个样例中，小俞同学拿走了100和1，你拿走了10。

在第二个样例中，小俞同学那走了2，8，6，5，9，你拿走了4，7，1，3。

来源

教学题