Koniec kola: 11. február 2019 23:59
20 days
Počet bodov:
Popis:  12b
Program:  8b

Baklažán a Buj sa hrajú hru. Zoberú balíček kariet a rozdelia ho na kôpky. Každá karta má na sebe napísané číslo predstavujúce body. Potom striedavo ťahajú z kôpok, pričom hráč na ťahu si vždy zvolí z ktorej kôpky odoberie kartu. Aby to nebolo príliš zložité, tak sa dohodli, že Baklažán bude brať kartu iba z vrchu a Buj iba zo spodu. Hra sa končí vtedy, keď sa minú karty a vyhráva ten s najväčším súčtom bodov.
Obaja majú ale veľa povinnosti v škole. Chceli by vás teda poprosiť aby ste zopár hier odohrali za nich. Odkazujú, že by obaja hrali optimálne.

Úloha

Zistite koľko bodov bude mať Baklažán a Buj po skončení hry ak obaja budú hrať optimálne. Hru vždy začína Baklažán.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) \((1 \leq n \leq 100)\), počet kôpok kariet. Za ním nasleduje \(n\) riadkov. V každom nasledujúcom riadku je číslo \(s_{i}\) \((1 \leq s_{i} \leq 100)\) označujúce počet kariet v \(i\)-tej kôpke. Za ním nasleduje \(s_{i}\) čísel \(c_{1}, c_{2}, ..., c_{s_{i}}\), hodnoty kariet od vrchu kôpky až po spodok. Pre ľubovolné \(c_{k}\) platí, \((1 \leq c_{k} \leq 1000)\).

Čiastočné body môžete získať v sade 1, kde je vždy počet kôpok rovný \(1\). Pre sadu 2 platí, že počet kôpok je \(2\).

Formát výstupu

Na výstup vypíšte dve čísla. Počet bodov Baklažána a počet bodov Buja po ukončení hry.

Príklady

Input:

2
1 100
2 1 10

Output:

101 10

Baklažán si zobral katru 100, Buj 10 a nakoniec Baklažán 1.

Input:

1
9 2 8 6 5 9 4 7 1 3

Output:

30 15

Baklažán by si zobral karty 2, 8, 6, 5, 9 a Buj 3, 1, 7, 4.

Input:

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

Output:

18 18

Hra by mohla prebiehať napríklad takto:
Baklažán zoberie kartu z tretej kôpky (skóre 5:0)
Bui zoberie kartu z druhej kôpky (skóre 5:7)
Baklažán zoberie kartu z druhej kôpky (skóre 13:7)
Bui zoberie kartu z tretej kôpky (skóre 13:13)
Baklažán zoberie kartu z tretej kôpky (skóre 17:15)
Bui zoberie kartu z prvej kôpky (skóre 17:15)
Baklažán zoberie kartu z prvej kôpky (skóre 18:15)
Bui zoberie kartu z prvej kôpky (skóre 18:18)

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.