### PROBLEM LINK:

**Author:** Hruday Pabbisetty

**Tester:** Alexey Zayakin

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

None

### PROBLEM:

You’re given N sequence A_1, \dots, A_N, each containing N elements. You should pick one element from each sequence (element picked from A_i is E_i). E_i should be strictly greater than E_{i-1}. Your task is to compute maximum possible E_1+E_2+\dots+E_N or output -1 if it’s impossible to pick such sequence.

### QUICK EXPLANATION

Greedily take maximum possible E_i starting at E_n and ending at E_1.

### EXPLANATION:

Let’s look at E_N. If there is element in A_N greater than E_N then we should pick it since it will not change that E_i is increasing but it will increase the sum. So E_N shoud be maximum possible element in A_N. Continuing by induction we can see that for E_i we should pick largest possible element, i.e. E_i is largest among all A_i < E_{i+1}. In this way one can solve problem in O(N^2) by picking E_i from N^{th} to 1^{st} and finding largest acceptable A_i each time. Example of solution:

```
int e[n];
e[n - 1] = *max_element(a[n - 1], a[n - 1] + n);
int64_t sum = e[n - 1];
for(int i = n - 2; i >= 0; i--) {
e[i] = 0;
for(int j = 0; j < n; j++) {
if(a[i][j] < e[i + 1]) {
e[i] = max(e[i], a[i][j]);
}
}
if(e[i] == 0) {
cout << -1 << endl;
return;
}
sum += e[i];
}
cout << sum << endl;
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.