3028 - 小俞同学的游戏
Time Limit : 1 秒
Memory Limit : 128 MB
一天,小俞同学突然之间就很没意思,于是她找来了你来玩游戏。她拿来了一堆卡片,把上面都写上了数字,并且把它们分成n摞。游戏的规则是这样的,你俩只可以从一摞牌的上面取一张或者是下面取一张(她想取上面的,于是你只好取下面的了)。
轮流取牌,你们也可以取不同的一摞的牌,只要遵守上面的规则即可。由于规则是她想出来的,所以,也是她先取牌。你俩都非常的聪明,都能用最优的策略来玩游戏,现在由你来算出最后的得分。
Input
第一行一个整数n(1<=n<=100).
第二行的第一个整数m代表每一摞有多少张牌(1<=m<=100),接下来m个整数Ci,代表第i张上面的分数(1<=Ci<=1000)
Output
一行两个整数p和q,代表小俞同学的得分和你的得分。
Examples
Input Format
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
Output Format
101 10 30 15 18 18 7000 7000