#include "bits/stdc++.h"
#include "tickets.h"
#define pb push_back
using namespace std;
const long long inf = 1e15;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
if(m == 1){
long long val = 0;
vector<int> arr;
for(int i = 0; i < n; i++){
arr.pb(x[i][0]);
val += x[i][0];
ans[i][0] = 0;
}
sort(arr.begin(), arr.end());
for(int i = 0; i < n/2; i++){
val -= arr[i] * 2;
}
allocate_tickets(ans);
return val;
}
else if(k == 1){
vector<int> mini(n), maxi(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(x[i][j] > x[i][maxi[i]]){
maxi[i] = j;
}
if(x[i][j] < x[i][mini[i]]){
mini[i] = j;
}
}
}
vector<vector<long long> > dp(n+1, vector<long long>(n/2+2, -inf));
vector<vector<pair<long long, long long> > > par(n+1, vector<pair<long long, long long> >(n/2+2));
dp[0][0] = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= min(i, n/2); j++){
if(dp[i][j] + x[i][maxi[i]] > dp[i+1][j+1]){
dp[i+1][j+1] = dp[i][j] + x[i][maxi[i]];
par[i+1][j+1] = {i, j};
}
if(dp[i][j] - x[i][mini[i]] > dp[i+1][j]){
dp[i+1][j] = dp[i][j] - x[i][mini[i]];
par[i+1][j] = {i, j};
}
}
}
vector<vector<int> > ans(n, vector<int>(m, -1));
pair<int, int> now = {n, n/2};
while(now != make_pair(0, 0)){
pair<int, int> nxt = par[now.first][now.second];
if(now.second == nxt.second){
ans[nxt.first][mini[nxt.first]] = 0;
}
else{
ans[nxt.first][maxi[nxt.first]] = 0;
}
now = nxt;
}
allocate_tickets(ans);
return dp[n][n/2];
}
return 0;
}
