题目描述

桌子上有 $n$ 堆牌。每张牌上都有一个正整数。Ciel 可以从任何非空牌堆的顶部取出一张牌，Jiro 可以从任何非空牌堆的底部取出一张牌。Ciel 先取，当所有的牌堆都变空时游戏结束。他们都想最大化他所拿牌的分数（即每张牌上正整数的和）。问他们所拿牌的分数分别是多少？

输入格式

第一行一个整数 $n$，$1\le n\le 100$。

接下来 $n$ 行，每行第一个整数 $s_i$，表示第 $i$ 堆牌的数量，后面 $s_i$ 个整数 $c_j$，表示这堆牌中第 $j$ 张牌上的数字，$1\le s_i\le 100$，$1\le c_j\le 1000$。

输出格式

分别输出 Ciel 和 Jiro 拿到的牌的分数，用一个空格分隔。

2
1 100
2 1 10

101 10

1
9 2 8 6 5 9 4 7 1 3

30 15

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

18 18

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

7000 7000