# CodeChef : January Challenge 2018 – Maximum Score

By | January 6, 2018

#### Maximum Score

Source: CodeChef

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.

### 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 ij

Subtask #1 (18 points): 1 ≤ Aij ≤ N for each valid ij

Subtask #2 (82 points): original constraints

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.

### Solution

Working on the solution.