Fox Ciel is playing a card game with her friend Fox Jiro. There are n piles of cards on the table. And there is a positive integer on each card.

The players take turns and Ciel takes the first turn. In Ciel's turn she takes a card from the top of any non-empty pile, and in Jiro's turn he takes a card from the bottom of any non-empty pile. Each player wants to maximize the total sum of the cards he took. The game ends when all piles become empty.

Suppose Ciel and Jiro play optimally, what is the score of the game?

Input

The first line contain an integer n (1 ≤ n ≤ 100). Each of the next n lines contains a description of the pile: the first integer in the line is si (1 ≤ si ≤ 100) — the number of cards in the i-th pile; then follow si positive integers c1, c2, ..., ck, ..., csi (1 ≤ ck ≤ 1000) — the sequence of the numbers on the cards listed from top of the current pile to bottom of the pile.

Output

Print two integers: the sum of Ciel's cards and the sum of Jiro's cards if they play optimally.

Examples

Input

2
1 100
2 1 10


Output

101 10


Input

1
9 2 8 6 5 9 4 7 1 3


Output

30 15


Input

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


Output

18 18


Input

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


Output

7000 7000

Note

In the first example, Ciel will take the cards with number 100 and 1, Jiro will take the card with number 10.

In the second example, Ciel will take cards with numbers 2, 8, 6, 5, 9 and Jiro will take cards with numbers 4, 7, 1, 3.
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class FoxAndCardGame {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int[] val = new int[2];
        ArrayList<Integer> centers = new ArrayList<>();
        /*
        Hmm doesn't feel very safe, but intuition is that we can first consider a
        game with one pile: in this case, we alternate top half and bottom. If odd,
        first player gets middle.

        But, if we have two piles, we can imagine that if a certain player has
        bad cards on their side of the piles, then they would want to dig through
        one pile to get to better cards. We can argue that the other player can
        always defend against this, since they just counter. So, no matter what,
        we're stuck with the cards we have. If it happens we have better cards,
        than we can defend against them in the same way.
        We don't know what the order is, but we know that regardless we can always
        protect our halves of the piles.

        If we do anything but do it pile by pile, we are giving the opponent
        an opportunity to invade our halves. We can always swap any move on a different
        pile with a move that attacks the same pile they are picking. Eventually,
        we'll get the same sum of our halves, but having played more defensively!
        This argument works by symmetry for the opponent too.

        Now, if there are odd elements, those are automatically available whoever
        gets to go first on a given pile. So, really the only mobility in the game
        is who gets which middle pieces (those will alternate in ownership). So,
        at each choice of which middle piece to go for, the person playing can
        greedily select the highest. Anything else would be necessarily worse. So,
        it'll just alternate from there.

        */
        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            int[] piles = sc.nextInts(S);
            if (S % 2 == 1) {
                centers.add(piles[S / 2]);
                piles[S / 2] = 0;
            }
            for (int j = 0; j < S; j++) {
                if (j < S / 2) {
                    val[0] += piles[j];
                }
                else {
                    val[1] += piles[j];
                }
            }
        }
        Collections.sort(centers, Collections.reverseOrder());
        int turn = 0;
        for (int v : centers) {
            val[turn] += v;
            turn ^= 1;
        }
        out.println(val[0] + " " + val[1]);
        out.close();
    }

    static class FastScanner {
        private int BS = 1<<16;
        private char NC = (char)0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
}