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.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	chef = 0
	ans = []
	for i in range(0, n):
		l = list(map(int, input().split()))
		c = l[0]
		if c % 2 == 0:
			for i in range(1, len(l) // 2 + 1):
				chef = chef + l[i]
			continue
		for i in range(1, len(l) // 2):
			chef = chef + l[i]
		ans.append(l[len(l) // 2])
	ans.sort(reverse=True)
	for i in range(len(ans)):
		if i % 2 == 0:
			chef = chef + ans[i]
	print(chef)


T = int(input())
for _ in range(T):
	n = int(input())
	s = 0
	temp = []
	for _ in range(n):
		l = list(map(int, input().split()))
		if l[0] % 2 == 0:
			s += sum(l[1:len(l) // 2 + 1])
		else:
			s += sum(l[1:len(l) // 2])
			temp.append(l[len(l) // 2])
	temp.sort(reverse=True)
	s += sum(temp[::2])
	print(s)


import math
for _ in range(int(input())):
	n = int(input())
	x = 0
	mi = []
	for i in range(n):
		l = list(map(int, input().split()))
		c = l[0]
		l1 = l[1:]
		d = math.floor(c / 2)
		s = sum(l1[:d])
		x = x + s
		if c % 2 != 0:
			mi.append(l1[d])
	mi.sort(reverse=True)
	for i in range(len(mi)):
		if (i + 1) % 2 != 0:
			x = x + mi[i]
	print(x)


import math
for _ in range(int(input())):
	n = int(input())
	x = 0
	for i in range(n):
		l = list(map(int, input().split()))
		c = l[0]
		l1 = l[1:]
		d = math.ceil(c / 2)
		s = sum(l1[:d])
		x = x + s
		l1 = []
		c = 0
		d = 0
	print(x)


for _ in range(int(input())):
	(chef, f) = (0, [])
	for j in range(int(input())):
		k = list(map(int, input().split()))
		for r in range(1, k[0] // 2 + 1):
			chef += k[r]
		if k[0] % 2 == 1:
			f.append(k[k[0] // 2 + 1])
	f.sort(reverse=True)
	for p in range(0, len(f), 2):
		chef += f[p]
	print(chef)


test = int(input())
dic = {}
for _ in range(test):
	dic = {}
	n = int(input())
	for i in range(n):
		a = input().split()
		l = [int(a[i]) for i in range(1, int(a[0]) + 1)]
		dic[i] = l
	c = 0
	lg = []
	for i in dic:
		c += len(dic[i])
	chef = {i: dic[i][0] for i in range(n)}
	ram = {i: dic[i][len(dic[i]) - 1] for i in range(n)}
	i = 0
	ans = 0
	while i < c:
		if i % 2 == 0:
			var = min(chef, key=chef.get)
			ans += chef[var]
			if len(dic[var]) == 1:
				chef.pop(var)
				ram.pop(var)
				dic[var].pop(0)
			else:
				dic[var].pop(0)
				chef[var] = dic[var][0]
		else:
			var = min(ram, key=ram.get)
			lg = len(dic[var]) - 1
			if lg == 0:
				chef.pop(var)
				ram.pop(var)
			else:
				dic[var].pop(lg)
				ram[var] = dic[var][lg - 1]
		i += 1
	print(ans)


for _ in range(int(input())):
	chef = 0
	for j in range(int(input())):
		k = list(map(int, input().split()))
		if k[0] % 2 == 0:
			for r in range(1, k[0] // 2 + 1):
				chef += k[r]
		else:
			for r in range(1, k[0] // 2 + 2):
				chef += k[r]
	print(chef)


for _ in range(int(input())):
	n = int(input())
	(l, l1) = ([], [])
	l3 = []
	s = 0
	for i in range(n):
		l2 = list(map(int, input().split()))
		n = l2[0]
		l2 = l2[1:]
		if n % 2 == 0:
			s += sum(l2[:len(l2) // 2])
		else:
			l.append(sum(l2[:len(l2) // 2]))
			l.append(sum(l2[:len(l2) // 2 + 1]))
			l1.append(l)
			l = []
			l3.append(l1[len(l1) - 1][1] - l1[len(l1) - 1][0])
	l4 = l3.copy()
	for i in range(len(l3)):
		if i < len(l3) // 2:
			t = l3.index(min(l3))
			s += min(l1[t])
			l3[t] = 99999
		else:
			t = l4.index(max(l4))
			s += max(l1[t])
			l4[t] = 0
	print(s)


for _ in range(int(input())):
	s = 0
	l1 = []
	for i in range(int(input())):
		l = list(map(int, input().split()))
		n = l[0]
		l = l[1:]
		if n % 2 == 0:
			s += sum(l[:n // 2])
		else:
			l1.append(l)
	(l2, l3) = ([], [])
	for i in range(len(l1)):
		l2.append(sum(l1[i][:len(l1[i]) // 2]))
		l2.append(sum(l1[i][:len(l1[i]) // 2 + 1]))
		l3.append(l2)
		l2 = []
	l3.sort()
	for i in range(len(l3)):
		if i < len(l3) // 2:
			s += min(l3[i])
		else:
			s += max(l3[i])
	print(s)


for _ in range(int(input())):
	n1 = int(input())
	sum1 = 0
	for i in range(n1):
		li = [int(i) for i in input().split()]
		li.pop(0)
		if len(li) % 2 == 0:
			n = len(li) // 2
		else:
			n = len(li) // 2 + 1
		sum1 += sum(li[:n])
	print(sum1)


for _ in range(int(input())):
	n = int(input())
	(chef, f) = (0, [])
	for i in range(n):
		l = list(map(int, input().split()))
		b = l[0]
		if b & 1:
			f.append(l[b // 2 + 1])
		for i in range(1, b // 2 + 1):
			chef += l[i]
	print(chef + sum(sorted(f)[::2]))