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