C. Лиса и игра в карты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лиса Сиель играет в карты со своим другом, лисом Джиро. На столе лежат n стопок карт и на каждой карте записано по положительному целому числу.

Игроки ходят по очереди, Сиель начинает. В свой ход она берет одну карту сверху любой непустой стопки. Джиро на своем ходу берет одну карту снизу любой непустой стопки. Каждый игрок хочет максимизировать общую сумму чисел на взятых им картах. Игра заканчивается, когда все стопки пустые.

С каким счетом закончится игра при условии, что Сиель и Джиро играют оптимально?

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 100). В каждой из следующих n строк записано описание одной стопки: первым в строке идет целое число si (1 ≤ si ≤ 100); число si обозначает количество карт в i-ой стопке; затем следуют si положительных целых чисел c1, c2, ..., ck, ..., csi (1 ≤ ck ≤ 1000) — последовательность чисел на картах в текущей стопке, перечисленных сверху вниз.

Выходные данные

Выведите два целых числа: сумму карт Сиель и сумму карт Джиро, если они играют оптимально.

Примеры
Входные данные
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
Примечание

В первом примере Сиель возьмет карты с числами 100 и 1, Джиро возьмет карту с числом 10.

Во втором примере Сиель возьмет карты с числами 2, 8, 6, 5, 9, а Джиро возьмет карты с числами 4, 7, 1, 3.