You are given N integer sequences A1, A2, ..., AN. Each of these sequences contains N elements. You should pick N elements, one from each sequence; let's denote the element picked from sequence Ai by Ei. For each i (2 ≤ i ≤ N), Ei should be strictly greater than Ei-1.
Compute the maximum possible value of E1 + E2 + ... + EN. If it's impossible to pick the elements E1, E2, ..., EN, print -1 instead.

-----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 N space-separated integers Ai1, Ai2, ..., AiN denoting the elements of the sequence Ai.

-----Output-----
For each test case, print a single line containing one integer — the maximum sum of picked elements.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 700
- 1 ≤ sum of N in all test-cases ≤ 3700
- 1 ≤ Aij ≤ 109 for each valid i, j

-----Subtasks-----
Subtask #1 (18 points): 1 ≤ Aij ≤ N for each valid i, j
Subtask #2 (82 points): original constraints

-----Example-----
Input:

1
3
1 2 3
4 5 6
7 8 9

Output:

18

-----Explanation-----
Example case 1: To maximise the score, pick 3 from the first row, 6 from the second row and 9 from the third row. The resulting sum is E1+E2+E3 = 3+6+9 = 18.

Difficulty: MEDIUM
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	lst = []
	for i in range(n):
		lst.append(list(map(int, input().split())))
	l = []
	prev = 1000000001
	for i in lst[::-1]:
		m = 0
		bl = False
		for j in i:
			if j < prev:
				m = max(j, m)
				bl = True
		if bl:
			l.append(m)
			prev = m
		else:
			break
	if len(l) == n:
		print(sum(l))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	arr = []
	n = int(input())
	for _ in range(n):
		arr.append(list(map(int, input().split(' '))))
	mx = max(arr[-1])
	sem = mx
	try:
		for i in range(n - 2, -1, -1):
			mx = max([j for j in arr[i] if j < mx])
			sem += mx
		print(sem)
	except ValueError:
		print(-1)


tc = int(input().strip())
for t in range(tc):
	n = int(input().strip())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().strip().split())))
	ans = 0
	ulim = 1000000000.0 + 1
	flag = True
	for i in range(n - 1, -1, -1):
		mx = -1
		for j in range(n):
			if ulim > arr[i][j]:
				if arr[i][j] > mx:
					mx = arr[i][j]
		if mx == -1:
			flag = False
			break
		else:
			ans += mx
			ulim = mx
	print(ans) if flag else print(-1)


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		t = list(map(int, input().split()))
		t.sort(reverse=True)
		a.append(t)
	a.reverse()
	f = a[0][0]
	count = 1
	mx = f
	for i in range(1, n):
		for j in range(n):
			if a[i][j] < mx:
				f += a[i][j]
				count += 1
				mx = a[i][j]
				break
	if count == n:
		print(f)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	rows = []
	for i in range(n):
		rows.append(list(map(int, input().split())))
	c = max(rows[-1])
	add = c
	try:
		for j in range(n - 2, -1, -1):
			c = max([i for i in rows[j] if i < c])
			add += c
		print(add)
	except ValueError:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	mat = []
	for _ in range(n):
		mat.append(sorted([int(a) for a in input().split()]))
	mat = mat[::-1]
	ans = max(mat[0])
	p = max(mat[0])
	for k in range(1, len(mat)):
		test = mat[k][::-1]
		f = False
		for val in test:
			if val < p:
				ans = ans + val
				f = True
				p = val
				break
		if not f:
			print(-1)
			break
	if f:
		print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	grid = []
	for j in range(n):
		temp = []
		temp = list(map(int, input().strip().split()))
		temp.sort()
		grid.append(temp)
	curr = max(grid[n - 1])
	total = curr
	for i in range(n - 2, 0 - 1, -1):
		flag = 0
		for j in range(n - 1, 0 - 1, -1):
			if grid[i][j] < curr:
				flag = 1
				curr = grid[i][j]
				total += curr
				break
		if flag == 0:
			total = -1
			break
	print(total)


for _ in range(int(input())):
	res = 0
	mat = []
	n = int(input())
	for _ in range(n):
		a = list(map(int, input().split()))
		mat.append(sorted(a))
	count = mat[n - 1][n - 1]
	temp = mat[n - 1][n - 1]
	c = 0
	k = 0
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if mat[i][j] < temp:
				count += mat[i][j]
				temp = mat[i][j]
				c += 1
				break
		if c == 0:
			print(-1)
			k = 1
			break
		else:
			c = 0
	if k == 0:
		print(count)


t = int(input())
while t > 0:
	l = []
	n = int(input())
	for i in range(n):
		l.append(list(map(int, input().split())))
	x = max(l[-1])
	w = 0
	s = x
	for i in range(n - 2, -1, -1):
		l[i].sort(reverse=True)
		q = 0
		for j in l[i]:
			if j < x:
				x = j
				q = 1
				s += x
				break
		if q == 0:
			w = 1
			print(-1)
			break
	if w == 0:
		print(s)
	t -= 1


try:
	for i in range(int(input())):
		nm = int(input())
		lst = []
		for j in range(nm):
			lst.append(sorted([int(x) for x in input().split()]))
		sm = lst[-1][-1]
		mx = lst[-1][-1]
		c = 1
		for m in range(nm - 2, -1, -1):
			for n in range(nm - 1, -1, -1):
				if lst[m][n] < mx:
					sm += lst[m][n]
					mx = lst[m][n]
					c += 1
					break
		if c == nm:
			print(sm)
		else:
			print(-1)
except:
	pass


for i in range(int(input())):
	n = int(input())
	b = []
	counter = 0
	for j in range(n):
		b.append(list(map(int, input().split())))
	c = max(b[-1])
	sum = c
	for k in range(1, n):
		for x in b[-k - 1]:
			if x < c and x > counter:
				counter = x
		if counter == 0:
			print(-1)
			sum = 0
			break
		else:
			sum = sum + counter
			c = counter
			counter = 0
	if sum != 0:
		print(sum)


def check(m, arr):
	s = -1
	for i in arr:
		if i < m:
			s = max(s, i)
	return s
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	s = max(a[-1])
	m = s
	for i in range(n - 2, -1, -1):
		m = check(m, a[i])
		if m != -1:
			s += m
		else:
			s = -1
			break
	print(s)


def maxScore():
	for t in range(int(input())):
		n = int(input())
		l = []
		for i in range(n):
			temp = sorted([int(x) for x in input().split()])
			l.append(temp)
		s = l[n - 1][n - 1]
		cdt_o = l[n - 1][n - 1]
		for i in range(n - 2, -1, -1):
			success = 1
			for j in range(n - 1, -1, -1):
				cdt_t = l[i][j]
				if cdt_t < cdt_o:
					s += cdt_t
					cdt_o = cdt_t
					break
				elif j == 0:
					success = 0
					break
				elif cdt_t >= cdt_o:
					continue
			if success == 0:
				break
		if success == 0:
			print(-1)
		else:
			print(s)
maxScore()


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l1 = list(map(int, input().split()))
		l1.sort()
		l.append(l1)
	ans = l1[-1]
	p = ans
	for i in range(n - 2, -1, -1):
		flag = 0
		for j in range(n - 1, -1, -1):
			if l[i][j] < p:
				p = l[i][j]
				ans += p
				flag = 1
				break
		if flag == 0:
			print(-1)
			flag = 2
			break
	if flag != 2:
		print(ans)


t = int(input())
for i in range(t):
	a = int(input())
	b = []
	c = []
	f = 0
	for j in range(a):
		b = list(map(int, input().split()))
		c.append(b)
	m = max(c[-1])
	s = m
	for k in range(a - 2, -1, -1):
		d = []
		for z in c[k]:
			if z < m:
				d.append(z)
		if len(d) > 0:
			m = max(d)
		else:
			f = -1
		s += m
	print(s if f == 0 else -1)


for j in range(int(input())):
	n = int(input())
	x = []
	for i in range(n):
		y = list(map(int, input().split()))
		y.sort()
		x.append(y)
	x.reverse()
	z = []
	a = max(x[0])
	z.append(a)
	v = 1
	for i in range(1, n):
		x[i].append(a)
		x[i].sort()
		b = x[i].index(a)
		if b - 1 >= 0:
			z.append(x[i][b - 1])
			a = x[i][b - 1]
		else:
			v = 0
			print(-1)
			break
	if v != 0:
		print(sum(z))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [0] * n
	for i in range(n):
		arr[i] = list(map(int, input().split()))
		arr[i].sort()
	cmax = 0
	curr = 0
	cbefore = math.inf
	for i in range(n - 1, -1, -1):
		ik = n - 1
		karr = arr[i]
		curr = karr[ik]
		while curr >= cbefore:
			ik = ik - 1
			if ik < 0:
				cmax = -1
				break
			curr = karr[ik]
		if cmax == -1:
			break
		cmax += curr
		cbefore = curr
	print(cmax)


for _ in range(int(input())):
	n = int(input())
	s = 0
	m = []
	for i in range(n):
		l = []
		l = [int(i) for i in input().split()]
		l.sort()
		m.append(l)
	answer = m[n - 1][n - 1]
	last = m[n - 1][n - 1]
	s = 1
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if m[i][j] < last:
				answer += m[i][j]
				last = m[i][j]
				s += 1
				break
	if s == n:
		print(answer)
	else:
		print(-1)


from bisect import bisect_left
for _ in range(int(input())):
	N = int(input())
	array = []
	for i in range(N):
		a = list(map(int, input().split()))
		a.sort()
		array.append(a)
	sm = array[-1][-1]
	current = array[-1][-1]
	possible = True
	for i in range(N - 2, -1, -1):
		idx = bisect_left(array[i], current)
		if idx == 0:
			possible = False
			break
		else:
			current = array[i][idx - 1]
			sm += array[i][idx - 1]
	if possible:
		print(sm)
	else:
		print(-1)


def fun(n, arr):
	s = 0
	temp = float('infinity')
	for i in range(n - 1, -1, -1):
		a = 0
		for j in range(0, n):
			if arr[i][j] > a and arr[i][j] < temp:
				a = arr[i][j]
		if a == 0:
			return -1
		temp = a
		s += a
	return s
for _ in range(int(input())):
	n = int(input())
	arr = [0] * n
	for i in range(n):
		arr[i] = list(map(int, input().strip().split()))
	print(fun(n, arr))


for i in range(int(input())):
	b = []
	for j in range(int(input())):
		a = [int(x) for x in input().split()]
		b.append(a)
	next = max(b[-1])
	sum = next
	for k in reversed(b[:-1]):
		su = max((y if y < next else -1 for y in k))
		if su == -1:
			sum = -1
			break
		sum += su
		next = su
	print(sum)


T = int(input())
for _ in range(T):
	N = int(input())
	l = []
	for __ in range(N):
		l.append(sorted(list(map(int, input().split()))))
	M = l[N - 1][N - 1]
	S = M
	c = 0
	f = 0
	for i in range(N - 2, -1, -1):
		for j in range(N - 1, -1, -1):
			if l[i][j] < M:
				M = l[i][j]
				S += M
				c += 1
				break
		if c == 0:
			print('-1')
			f += 1
			break
		else:
			c -= 1
	if f == 0:
		print(S)


for _ in range(int(input())):
	n = int(input())
	mat = []
	for x in range(n):
		mat.append([int(i) for i in input().split()])
	ans = [0] * n
	flag = True
	ans[-1] = max(mat[-1])
	for i in range(n - 2, -1, -1):
		for ele in mat[i]:
			if ele < ans[i + 1]:
				ans[i] = max(ans[i], ele)
		if ans[i] == 0:
			flag = False
			break
	if flag:
		print(sum(ans))
	else:
		print(-1)


def maxsc(m, n):
	from bisect import bisect_left
	dp = [[-1 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dp[0][i] = m[0][i]
	for i in range(1, n):
		for j in range(n):
			d = bisect_left(m[i - 1], m[i][j])
			if d > 0 and dp[i - 1][d - 1] != -1:
				dp[i][j] = max(dp[i][j], dp[i - 1][d - 1] + m[i][j])
	return max(dp[n - 1])
t = int(input())
for _ in range(t):
	n = int(input())
	m = []
	for i in range(n):
		L = list(map(int, input().split()))
		m.append(sorted(L))
	print(maxsc(m, n))


for _ in range(int(input())):
	n = int(input())
	score = []
	for i in range(n):
		a = list(map(int, input().split()))
		a.sort()
		score.append(a)
	score = score[::-1]
	maxx = max(score[0])
	p = max(score[0])
	for j in range(1, len(score)):
		b = score[j]
		b = sorted(b, reverse=True)
		for value in b:
			if value < p:
				maxx += value
				p = value
				break
		else:
			maxx = -1
			break
	print(maxx)


def largest_smaller_than(a, N, key):
	start = 0
	end = N
	ans = -1
	while end >= start:
		mid = (start + end) // 2
		if mid >= N or mid < 0:
			break
		elif a[mid] < key:
			ans = mid
			start = mid + 1
		elif a[mid] >= key:
			end = mid - 1
	if ans != -1:
		return a[ans]
	else:
		return -1
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = []
	for i in range(N):
		x = [int(i) for i in input().split()]
		A.append(sorted(x))
	start = float('inf')
	sum = 0
	for i in range(N - 1, -1, -1):
		start = largest_smaller_than(A[i], N, start)
		if start == -1:
			sum = -1
			break
		sum += start
	ans.append(sum)
for i in ans:
	print(i)


import sys

def compute(x):
	s = 0
	temp = sys.maxsize
	for i in range(len(x) - 1, -1, -1):
		f = 0
		for j in range(0, len(x)):
			if x[i][j] > f and x[i][j] < temp:
				f = x[i][j]
		if f == 0:
			return -1
		temp = f
		s += f
	return s
for _ in range(int(input())):
	n = int(input())
	x = []
	for _ in range(n):
		x.append(list(map(int, input().split())))
	print(compute(x))


testCases = int(input())
lines = 0
for _ in range(testCases):
	lines = int(input())
	arr = []
	for _ in range(lines):
		arr.append(sorted(list(map(int, input().split())), reverse=True))
	maximum = max(arr[lines - 1])
	choosen = maximum
	bool = True
	for index in range(lines - 2, -1, -1):
		secondBool = True
		for j in range(lines):
			if arr[index][j] < maximum:
				choosen += arr[index][j]
				maximum = arr[index][j]
				secondBool = False
				break
		if secondBool == True:
			bool = False
			break
	if bool == True:
		print(choosen)
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input())
	mat = []
	for _ in range(n):
		s = input().split()
		arr = [int(x) for x in s]
		arr.sort(reverse=True)
		mat.append(arr)
	mat.reverse()
	curr = mat[0][0]
	summ = curr
	counter = 1
	for i in range(1, n):
		for el in mat[i]:
			if el < curr:
				summ += el
				curr = el
				counter += 1
				break
	if counter == n:
		print(summ)
	else:
		print(-1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		a = list(map(int, input().split()))
		a.sort(reverse=True)
		l.append(a)
	su = l[n - 1][0]
	flag = True
	c = l[n - 1][0]
	j = 0
	if n > 1:
		for i in range(n - 2, -1, -1):
			j = 0
			while 1:
				if l[i][j] < su:
					su = l[i][j]
					c += l[i][j]
					break
				elif j + 1 < n:
					j += 1
				else:
					print(-1)
					flag = False
					break
			if not flag:
				break
		if flag:
			print(c)
	elif n == 1:
		print(c)


def score(qn):
	import math
	maximum = math.inf
	score = 0
	for i in reversed(range(0, len(qn))):
		temp = -1
		for j in qn[i]:
			if j > temp and j < maximum:
				temp = j
		if temp == -1:
			return -1
		else:
			score += temp
			maximum = temp
	return score
import sys
c = 0
for line in sys.stdin:
	if c == 0:
		t = int(line.strip())
		c = 2
	elif c % 2 == 0:
		new = line.split()
		N = int(new[0].strip())
		qn = []
		c = 5
		count = 1
	elif c == 5:
		a = list(map(int, line.split()))
		qn.append(a)
		count += 1
		if count == N + 1:
			c = 2
			print(score(qn))


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for _ in range(n):
		h = list(map(int, input().split()))
		h.sort()
		a.append(h)
	c = 1
	k = max(a[n - 1])
	s = k
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if k > a[i][j]:
				k = a[i][j]
				c += 1
				s += k
				break
	if c == n:
		print(s)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	l = []
	while n > 0:
		k = []
		k = [int(i) for i in input().split()]
		k = sorted(k)
		l.append(k)
		n -= 1
	count = [l[-1][-1]]
	flag = 0
	for i in range(len(l) - 2, -1, -1):
		for j in range(len(l) - 1, -1, -1):
			if l[i][j] < count[-1]:
				count.append(l[i][j])
				break
		else:
			flag = 1
			break
		if flag == 1:
			break
	if flag == 1:
		print(-1)
	else:
		print(sum(count))


for _ in range(int(input())):
	a = []
	n = int(input())
	for t in range(n):
		p = list(map(int, input().split()))
		a.append(p)
	c = [0] * n
	c[n - 1] = max(a[n - 1])
	f = 0
	s = 0
	for i in range(n - 2, -1, -1):
		c[i] = 0
		for j in range(n):
			if a[i][j] < c[i + 1]:
				c[i] = max(c[i], a[i][j])
		if c[i] == 0:
			f = 1
			break
		else:
			s += c[i]
	if f == 1:
		print(-1)
	else:
		print(s + c[n - 1])


test = int(input())
for _ in range(test):
	n = int(input())
	ls = []
	for _ in range(n):
		ls.append(sorted(list(map(int, input().split())), reverse=True))
	m = max(ls[n - 1])
	s = m
	d = 0
	for i in range(n - 2, -1, -1):
		f = 0
		for j in range(n):
			if ls[i][j] < m:
				s += ls[i][j]
				m = ls[i][j]
				f = 1
				break
		if f == 0:
			d = 1
			break
	if d == 0:
		print(s)
	else:
		print(-1)


t = int(input())

def func(n, l, cnt, cur):
	for i in range(n - 2, -1, -1):
		if min(l[i]) >= cur:
			return -1
			break
		else:
			l[i] = [k for k in l[i] if k < cur]
			tmp = max(l[i])
			cnt += tmp
			cur = tmp
	return cnt
for _ in range(t):
	l = []
	n = int(input())
	for _ in range(n):
		s = input().split(' ')
		arr = [int(i) for i in s]
		l.append(arr)
	cnt = 0
	cnt += max(l[-1])
	cur = max(l[-1])
	print(func(n, l, cnt, cur))


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		x = list(map(int, input().split()))
		x.sort()
		a.append(x)
	m = max(a[-1])
	s = m
	c = 1
	for i in range(n - 2, -1, -1):
		for j in range(len(a[i]) - 1, -1, -1):
			if a[i][j] < m:
				m = a[i][j]
				s += m
				c += 1
				break
	if c == n:
		print(s)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(0, n):
		l1 = [int(l1) for l1 in input().split()]
		l.append(l1)
	s = max(l[-1])
	m = max(l[-1])
	g = 0
	for i in range(n - 2, -1, -1):
		m1 = -1
		f = 0
		for j in l[i]:
			if j < m and j > m1:
				f = 1
				m1 = j
		if f == 0:
			print(-1)
			g = 1
			break
		s += m1
		m = m1
	if g == 0:
		print(s)


for _ in range(int(input())):
	n = int(input())
	l = [[*map(int, input().split())] for i in range(n)]
	for i in range(n):
		l[i].sort()
	val = l[-1][-1]
	ans = val
	flag = True
	for i in range(n - 2, -1, -1):
		j = n - 1
		flag1 = False
		while j >= 0:
			if l[i][j] < val:
				val = l[i][j]
				flag1 = True
				break
			else:
				j -= 1
		if flag1:
			ans += l[i][j]
			val = l[i][j]
		else:
			flag = False
			break
	if flag:
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append([int(i) for i in input().split()])
	ex = [max(arr[n - 1])]
	for i in range(n - 2, -1, -1):
		e = -1
		for j in range(n - 1, -1, -1):
			if arr[i][j] < ex[len(ex) - 1]:
				e = max(e, arr[i][j])
		if e == -1:
			print(-1)
			break
		else:
			ex.append(e)
	else:
		print(sum(ex))


def abc(l, n):
	l.reverse()
	x = l[0][-1]
	sum = x
	for i in range(1, n):
		if l[i][0] >= x:
			return -1
		for j in range(n - 1, -1, -1):
			if l[i][j] < x:
				sum += l[i][j]
				x = l[i][j]
				break
	return sum
t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		x = list(map(int, input().split()))
		x.sort()
		l.append(x)
	print(abc(l, n))


for _ in range(int(input())):
	n = int(input())
	s = 0
	mat = []
	for i in range(n):
		a = []
		a = [int(i) for i in input().split()]
		a.sort()
		mat.append(a)
	ans = mat[n - 1][n - 1]
	last = mat[n - 1][n - 1]
	s = 1
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if mat[i][j] < last:
				ans += mat[i][j]
				last = mat[i][j]
				s += 1
				break
	if s == n:
		print(ans)
	else:
		print(-1)


import sys
ntests = int(sys.stdin.readline().strip())
while ntests > 0:
	ntests -= 1
	N = int(sys.stdin.readline().strip())
	state = [(0, 0)]
	for r in range(0, N):
		fields = list(map(int, sys.stdin.readline().strip().split()))
		fields.sort()
		i = len(state) - 1
		j = len(fields) - 1
		nstate = []
		while i >= 0 and j >= 0:
			if fields[j] > state[i][0]:
				nstate.insert(0, (fields[j], fields[j] + state[i][1]))
				j -= 1
			else:
				i -= 1
		state = nstate
	if len(state) > 0:
		print(state[-1][1])
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	for i in range(n):
		arr[i].sort()
	m = arr[n - 1][n - 1]
	ans = arr[n - 1][n - 1]
	f = 1
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if arr[i][j] < m:
				m = arr[i][j]
				ans += m
				break
			if j == 0:
				f = 0
				break
	if f:
		print(ans)
	else:
		print(-1)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		b = list(map(int, input().split()))
		b.sort()
		a.append(b)
	ans = a[-1][-1]
	flag = a[-1][-1]
	for i in range(n - 2, -1, -1):
		flag1 = 1
		for j in range(n - 1, -1, -1):
			if a[i][j] < flag:
				flag1 = 0
				ans += a[i][j]
				flag = a[i][j]
				break
		if flag1 == 1:
			print(-1)
			break
	if flag1 != 1:
		print(ans)


for _ in range(int(input())):
	k = 0
	x = int(input())
	a = list()
	p = [0] * x
	for i in range(x):
		a.append(list(map(int, input().split())))
	p[-1] = max(a[-1])
	flag = 0
	for i in range(x - 2, -1, -1):
		q = sorted(a[i])
		m = 0
		for j in range(x - 1, -1, -1):
			if q[j] < p[i + 1]:
				p[i] = q[j]
				m = 1
				break
		if m == 0:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		print(sum(p))


import bisect
for _ in range(int(input())):
	N = int(input())
	M = []
	for i in range(N):
		A = list(map(int, input().split()))
		A.sort()
		M.append(A)
	E = [M[-1][-1]]
	for i in range(N - 2, -1, -1):
		j = bisect.bisect_left(M[i], E[-1]) - 1
		if j < 0:
			break
		E.append(M[i][j])
	if len(E) < N:
		print(-1)
	else:
		print(sum(E))


import numpy as np
for _ in range(int(input())):
	n = int(input())
	arr = np.zeros((n, n), int)
	for i in range(n):
		line = np.array(list(map(int, input().split())))
		arr[i] = line
	s = 0
	previous = 1000000000.0 + 1
	for row in range(n - 1, -1, -1):
		previous = max((arr[row] < previous) * arr[row])
		if previous == 0:
			s = -1
			break
		s += previous
	print(s)


import numpy as np
T = int(input())
for case in range(T):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.reverse()
	ans = max(l[0])
	m = max(l[0])
	for i in range(1, n):
		a = np.array(l[i])
		a = a[a < m]
		if len(a) == 0:
			ans = -1
			break
		else:
			m = max(a)
			ans += m
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	matrix = []
	for n in range(N):
		matrix.append([int(i) for i in input().split()])
	E = [max(matrix[N - 1])]
	for i in range(N - 2, -1, -1):
		e = -1
		for j in range(N - 1, -1, -1):
			if matrix[i][j] < E[len(E) - 1]:
				e = max(e, matrix[i][j])
		if e == -1:
			print(-1)
			break
		else:
			E.append(e)
	else:
		print(sum(E))


t = int(input())
for cases in range(t):
	n = int(input())
	lis = []
	for i in range(n):
		lis1 = sorted(list(map(int, input().split())))
		lis.append(lis1)
	summ = lis[-1][-1]
	maxx = summ
	c = 1
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if lis[i][j] < maxx:
				maxx = lis[i][j]
				c += 1
				summ += lis[i][j]
				break
	if c == n:
		print(summ)
	else:
		print(-1)
	print()


T = int(input())
for _ in range(T):
	n = int(input())
	seq = []
	score_list = []
	for _ in range(n):
		res = list(map(int, input().split()))
		seq.append(res)
	seq.reverse()
	for l in seq:
		if len(score_list) == 0:
			score_list.append(max(l))
		else:
			l.sort(reverse=True)
			for i in l:
				if i < score_list[len(score_list) - 1]:
					score_list.append(i)
					break
				elif i == l[len(l) - 1] and i >= score_list[len(score_list) - 1]:
					score_list.append(-1)
	if min(score_list) == -1:
		print(-1)
	else:
		print(sum(score_list))


t = int(input())
for T in range(t):
	l = []
	n = int(input())
	c = 1
	for i in range(n):
		a = [int(x) for x in input().split()]
		a.sort()
		l.append(a)
	ans = l[n - 1][n - 1]
	ele = ans
	for i in range(len(l) - 2, -1, -1):
		c = 1
		for j in range(n - 1, -1, -1):
			if l[i][j] < ele:
				ele = l[i][j]
				ans += ele
				c = 0
				break
		if c == 1:
			ans = -1
			break
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list()
	for i in range(n):
		A.append(sorted(list(map(int, input().split())), reverse=True))
	Ans = A[n - 1][0]
	prev = Ans
	flag = False
	for i in range(n - 2, -1, -1):
		flag = True
		for j in A[i]:
			if j < prev:
				flag = False
				Ans += j
				prev = j
				break
		if flag:
			break
	if flag:
		print(-1)
	else:
		print(Ans)


for i in range(int(input())):
	a = int(input())
	b = []
	c = []
	cnt = 0
	fl = 0
	for i in range(a):
		b = list(map(int, input().split()))
		c.append(b)
	mx = max(c[-1])
	sm = mx
	for i in range(a - 2, -1, -1):
		d = []
		for j in c[i]:
			if j < mx:
				d.append(j)
		if len(d) > 0:
			mx = max(d)
		else:
			fl = -1
		sm += mx
	if fl == 0:
		print(sm)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		x = list(map(int, input().split()))
		l.append(x)
	max1 = max(l[len(l) - 1])
	sum1 = max1
	c = len(l) - 2
	while c >= 0:
		z = l[c]
		z.sort(reverse=True)
		p = 0
		for i in z:
			if i < max1:
				sum1 += i
				max1 = i
				p = 1
				break
		if p == 0:
			sum1 = -1
			break
		c -= 1
	print(sum1)


t = int(input())
while t:
	n = int(input())
	l = []
	for i in range(n):
		l1 = list(map(int, input().split()))
		l1 = sorted(l1)
		l.append(l1)
	count = l[n - 1][n - 1]
	m = l[n - 1][n - 1]
	c = 0
	k = 0
	for i in range(n - 2, -1, -1):
		for j in range(n - 1, -1, -1):
			if l[i][j] < m:
				count += l[i][j]
				m = l[i][j]
				c += 1
				break
		if c == 0:
			print(-1)
			k += 1
			break
		else:
			c -= 1
	if k == 0:
		print(count)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = []
	if n == 1:
		s = int(input())
		print(s)
	else:
		for i in range(n):
			a = list(map(int, input().split()))
			a.sort()
			l.append(a)
		m = l[-1][-1]
		flag = 1
		sum = m
		for j in range(n - 2, -1, -1):
			b = False
			for k in range(n - 1, -1, -1):
				if l[j][k] < m:
					m = l[j][k]
					sum += m
					b = True
					break
			if b == False:
				break
		if not b:
			print(-1)
		else:
			print(sum)


for _ in range(int(input())):
	n = int(input())
	lis = []
	for i in range(n):
		a = list(map(int, input().split()))
		lis.append(a)
	for i in range(n):
		lis[i].sort()
	sum = lis[n - 1][n - 1]
	tmp = lis[n - 1][n - 1]
	f = 0
	g = 0
	i = n - 2
	while i >= 0:
		j = n - 1
		f = 0
		while j >= 0:
			if lis[i][j] < tmp:
				sum += lis[i][j]
				tmp = lis[i][j]
				f = 1
				break
			j -= 1
		if f == 0:
			g = 1
			break
		i -= 1
	if g == 0:
		print(sum)
	else:
		print('-1')


def function(a, N):
	acc = max(a[N - 1])
	en = acc
	for i in range(N - 2, -1, -1):
		max_yet = -1
		for elem in a[i]:
			if elem > max_yet and elem < en:
				max_yet = elem
		if max_yet == -1:
			print(-1)
			return
		en = max_yet
		acc += en
	print(acc)
T = int(input())
for testcase in range(T):
	N = int(input())
	a = []
	for i in range(N):
		ai = list(map(int, input().split(' ')))
		ai.sort()
		a.append(ai)
	function(a, N)


T = int(input())
for _ in range(T):
	N = int(input())
	l = []
	S = 0
	f = 0
	for __ in range(N):
		l.append(list(map(int, input().split())))
	y = max(l[N - 1])
	S += y
	for i in range(N - 2, -1, -1):
		c = 0
		for j in range(0, N):
			if l[i][j] > c and l[i][j] < y:
				c = l[i][j]
		if c == 0:
			f += 1
			break
		else:
			S += c
			y = c
	if f > 0:
		print('-1')
	else:
		print(S)


t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	for k in range(n):
		a = [int(z) for z in input().split(' ')]
		a.sort()
		arr.append(a)
	old = 10 ** 9 + 1
	c = 0
	sumo = 0
	for k in range(n - 1, -1, -1):
		for z in range(n - 1, -1, -1):
			val = arr[k][z]
			if val < old:
				sumo += val
				c += 1
				old = val
				break
	if c == n:
		print(sumo)
	else:
		print(-1)


T = int(input())
for i in range(T):
	N = int(input())
	c = []
	for j in range(N):
		s = list(map(int, input().split()))
		s.sort()
		c.append(s)
	t = 1
	k = max(c[N - 1])
	r = k
	for i in range(N - 2, -1, -1):
		for j in range(N - 1, -1, -1):
			if k > c[i][j]:
				k = c[i][j]
				t += 1
				r += k
				break
	if t == N:
		print(r)
	else:
		print(-1)


def fun(a, n):
	t = max(a[n - 1])
	s = 0
	s += t
	for i in range(n - 2, -1, -1):
		l = []
		for j in range(n):
			if t > a[i][j]:
				l.append(a[i][j])
		if l == []:
			return -1
		t = max(l)
		s += t
	return s
t = int(input())
for p in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().strip().split()))[:n])
	print(fun(a, n))


for u in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(sorted(list(map(int, input().split())), reverse=True))
	m = max(l[n - 1])
	s = m
	d = 0
	for i in range(n - 2, -1, -1):
		f = 0
		for j in range(n):
			if l[i][j] < m:
				s += l[i][j]
				m = l[i][j]
				f = 1
				break
		if f == 0:
			d = 1
			break
	if d == 0:
		print(s)
	else:
		print(-1)