Chef is in need of money, so he decided to play a game with Ramsay. In this game, there are $N$ rows of coins (numbered $1$ through $N$). For each valid $i$, the $i$-th row contains $C_i$ coins with values $A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}$.
Chef and Ramsay alternate turns; Chef plays first. In each turns, the current player can choose one row that still contains coins and take one of the coins remaining in this row. Chef may only take the the first (leftmost) remaining coin in the chosen row, while Ramsay may only take the last (rightmost) remaining coin in the chosen row. The game ends when there are no coins left.
Each player wants to maximise the sum of values of the coins he took. Assuming that both Chef and Ramsay play optimally, what is the maximum amount of money (sum of values of coins) Chef can earn through this game?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains an integer $C_i$, followed by a space and $C_i$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum amount of money Chef can earn.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^4$
- $1 \le C_i \le 10$ for each valid $i$
- $1 \le A_{i, j} \le 10^5$ for each valid $i$ and $j$

-----Subtasks-----
Subtask #1 (20 points): $N = 1$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
2
4 5 2 3 4
2 1 6

-----Example Output-----
8

-----Explanation-----
Example case 1: One optimal sequence of moves is: Chef takes the coin with value $5$, Ramsay takes $4$, Chef takes $2$, Ramsay takes $3$, Chef takes $1$ and Ramsay takes $6$. At the end, Chef has $5+2+1 = 8$ units of money.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'for _ in range(int(input())):\n s=0\n l1=[]\n for i in range(int(input())):\n  l=list(map(int,input().split()))\n  n=l[0]\n  l=l[1:]\n  if n%2==0:\n   s+=sum(l[:n//2])\n  else:\n   l1.append(l)\n l2,l3=[],[]\n for i in range(len(l1)):\n  l2.append(sum(l1[i][:len(l1[i])//2]))\n  l2.append(sum(l1[i][:len(l1[i])//2+1]))\n  l3.append(l2)\n  l2=[]\n l3.sort()\n for i in range(len(l3)):\n  if i<len(l3)//2:\n   s+=min(l3[i])\n  else:\n   s+=max(l3[i])\n print(s)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13731