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

Subtasks

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

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.

Solution

Working on the solution.