题目描述

小 F 和小 W 有 $n$ 个双向队列。她们很无聊，于是在上面玩起了游戏。

小 F 先手，小 W 后手，两个人轮流行动。

小 F 的每个回合她可以选择一个双向队列，从队首弹出一个元素并获得那个元素的分数。

小 W 的每个回合她可以选择一个双向队列，从队尾弹出一个元素并获得那个元素的分数。

两个人的目标都是最大化自己的分数，假设两个人都做出最优选择，请计算两个人获得的分数。

输入格式

第一行一个整数 $n$ 。

接下来的 $n$ 行每行描述一个双向队列，每行首先是一个整数 $\ell_i$ 表示第 $i$ 个双向队列的长度，接下来 $\ell_i$ 个整数 $q_{i,j}$ ($1\leq q_{i,j}\leq 1000$) ，表示该双向队列中每个元素的分数。这 $\ell_i$ 个整数中的第一个是队首，最后一个是队尾。

输出格式

输出两个空格隔开的整数 $a,b$ ， $a$ 表示最优策略下小 F 的分数， $b$ 代表小 W 的分数。

样例 1 输入

2
1 1
2 2 3

样例 1 输出

3 3

样例 2 输入

deque2.in

样例 2 输出

deque2.out

数据范围

对于 $20\%$ 的数据， $n\leq 5,\max \ell_i\leq 5$ 。

对于 $40\%$ 的数据， $\max \ell_i\leq 5$ 。

对于 $100\%$ 的数据， $n,\max \ell_i\leq 100$ 。