← 返回题目列表

Codeforces · 388/C

C. 狐狸和纸牌游戏

中文机器翻译题面 查看原题

Fox Ciel 正在和她的朋友 Fox Jiro 玩纸牌游戏。桌子上有n堆卡片。每张卡片上都有一个正整数。

玩家轮流,夏尔先轮流。在夏尔的回合中,她从任何非空的牌堆的顶部拿一张牌,而在次郎的回合中,他从任何非空的牌堆的底部拿一张牌。每个玩家都想最大化他所拿的牌的总和。当所有牌堆变空时游戏结束。

假设 Ciel 和 Jiro 发挥最佳,比赛得分是多少?

输入

第一行包含一个整数 n (1 ≤ n ≤ 100)。接下来的 n 行中的每一行都包含对该堆牌的描述:该行中的第一个整数是 si (1 ≤ si ≤ 100) — 第 i 堆牌中的牌数;然后跟随 si 个正整数 c1, c2, ..., ck, ..., csi (1 ≤ ck ≤ 1000) — 从当前牌堆顶部到底部列出的卡片上的数字序列。

输出

打印两个整数:Ciel 的牌的总和以及 Jiro 的牌的总和(如果它们发挥最佳)。

示例

输入 #1

2
1 100
2 1 10

输出 #1

101 10

输入 #2

1
9 2 8 6 5 9 4 7 1 3

输出 #2

30 15

输入 #3

3
3 1 3 2
3 5 4 6
2 8 7

输出 #3

18 18

输入#4

3
3 1000 1000 1000
6 1000 1000 1000 1000 1000 1000
5 1000 1000 1000 1000 1000

输出#4

7000 7000

注意

在第一个示例中,Ciel 将拿走数字 100 和 1 的牌,Jiro 将拿走数字 10 的牌。

在第二个示例中,Ciel 将拿走数字 2、8、6、5、9 的牌,而 Jiro 将拿走数字 4、7、1、3 的牌。