Alice i Bob wybrali się razem do pizzeri, gdzie zamówili p pizz (wszystkie pizze zostały przyniesione w jednym momencie). Każda pizza jest pokrojona w standardowy sposób, czyli cięciami od środka do brzegu, przy czym poszczególne kawałki mogą mieć różne wielkosći. Oboje są bardzo głodni i chcieli by zjeść jak najwięcej. Alice i Bob na przemian wybierają po kawałku pizzy, który zjedzą przy czym o ile jest to możliwe wybierają kawałek pizzy z brzegu, czyli taki, którego już co najmniej jeden z sąsiadów został zjedzony. Sąsiad oznacza kawałek który ma wspólną krawędź z danym kawałkiem (każdy kawałek ma dokładnie 2 sąsiadów). Bob jest dżentelmenem, więc Alice wybiera pierwsza. Alice i Bob są sprytni i wybierają takie kawałki, żeby sumarycznie zjeść jak najwięcej. Ustal jaka jest sumaryczna wielkość wszystkich kawałków zjedzonych przez Alice i Boba.
Napisz program który:
W pierwszej linii wejścia znajduje sie jedna liczba całkowita p (1 ≤ p ≤ 500). W każdej z kolejnych p linii znajdują się opis jednej z pizz składający się z liczby k (1 ≤ k ≤ 500), oznaczająca ilości kawałków na które podzielono pizzę, po której następuje k liczb naturalnych a1 , a2 , . . . , ak (1 ≤ ai ≤ 1000 dla 1 ≤ i ≤ k) oznaczających wielkości kolejnych kawałków.
W jedynej linii wyjścia powinny znaleźć się dwie liczby całkowite, oznaczające sumaryczna wielkość wszystkich kawałków zjedzonych odpowiednio przez Alice i Boba.
2 5 3 4 5 1 2 6 1 2 3 1 2 2poprawnym wynikiem jest:
15 11
[Zgłoś rozwiązanie] [Moje zgłoszenia]