You are given N integer sequences A1, A2, …, AN. Each of these sequences contains Nelements. You should pick N elements, each from one 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.
- 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.
For each test case, print a single line containing one integer — the maximum sum of picked elements.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 700
- 1 ≤ sum of N in all test-cases ≤ 3700
- 1 ≤ Aij ≤ 109 for each valid i, j
Subtask #1 (18 points): 1 ≤ Aij ≤ N for each valid i, j
Subtask #2 (82 points): original constraints
Input: 1 3 1 2 3 4 5 6 7 8 9 Output: 18
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.
Working on the solution.