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: interview

Starter code:

Solutions:
t=int(input())
for _ in range(t):
 n=int(input())
 
 grid=[]
 for _ 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)
 
 
    
   
   
  


# cook your dish here
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)

# cook your dish here
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()
  


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)


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())):
 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)

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)

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)

# cook your dish here
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])


# cook your dish here
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])


# cook your dish here
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)

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)


# cook your dish here
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()


def score(qn):
 
 import math
 maximum = math.inf
 score = 0
 for i in reversed(list(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
 else:
  if 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))


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)


# cook your dish here
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)


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)


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 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)
 


# cook your dish here
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)

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())
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

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)


# cook your dish here
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)
 #print(l)
 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):
    #print(count)
    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=[]
 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))