#include "tickets.h"
#include "bits/stdc++.h"
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
if(m == 1) {
for(int i=0; i<n; i++) answer[i][0] = 0;
allocate_tickets(answer);
vector<int> ff;
for(int i=0; i<n; i++) ff.push_back(x[i][0]);
sort(ff.begin(), ff.end());
long long ss = 0;
for(int x: ff) ss += abs(x - ff[n / 2]);
return ss;
}
long long dp[n+1][n+1]; // number of max, index range
for(int i=0; i<=n; i++) {
for(int j=0; j<=n; j++) {
dp[i][j] = -1e16;
}
}
dp[0][0] = 0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
// choose max
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + x[j-1][m-1]);
// choose min
dp[i][j] = max(dp[i][j], dp[i][j-1] - x[j-1][0]);
}
}
int f = n/2;
for(int i=n; i>=1; i--) {
if(dp[f][i] == dp[f-1][i-1] + x[i-1][m-1]) {
answer[i-1][m-1] = 0;
f--;
}
else {
answer[i-1][0] = 0;
}
}
allocate_tickets(answer);
return dp[n / 2][n];
}
