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 的牌。