#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int N = 3e5+5;
const int MOD = 1e9+7;
const ll INF = 1e18+5;
#ifdef dremix
#define p2(x,y) cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto v : x)cerr<<v.F<<"-"<<v.S<<", ";cerr<<"}"<<endl;
#else
#define p2(x,y) {}
#define ppv(x) {}
#endif
long long find_maximum(int k, vector<vector<int> > x) {
int n = x.size();
int m = x[0].size();
vector<pi> arr;
int i,j;
pi idx[n];
for (i = 0; i < n; i++) {
int mini = MOD,maxi = -MOD;
for(j=0;j<m;j++){
if(x[i][j] < mini){
mini = x[i][j];
idx[i].F = j;
}
if(x[i][j] > maxi){
maxi = x[i][j];
idx[i].S = j;
}
}
arr.push_back({mini,maxi});
}
//sort(all(arr));
vector<vector<ll> > dp(n+1,vector<ll>(n/2+1,-INF));
/// dp[i][j] , at color i, took j minimums up to now
dp[0][0] = 0;
for(i=1;i<=n;i++){
/// take maximum only
dp[i][0] = dp[i-1][0] + arr[i-1].S;
for(j=1;j<=n/2;j++){
dp[i][j] = max(dp[i][j],dp[i-1][j] + arr[i-1].S);
dp[i][j] = max(dp[i][j],dp[i-1][j-1] - arr[i-1].F);
}
}
vector<vector<int> > answer(n,vector<int>(m,-1));
ll sum = dp[n][n/2];
i = n;
j = n/2;
while(i > 0){
if(dp[i][j] - arr[i-1].S == dp[i-1][j]){
answer[i-1][idx[i-1].S] = 0;
i--;
}
else{
assert(dp[i][j] + arr[i-1].F == dp[i-1][j-1]);
answer[i-1][idx[i-1].F] = 0;
i--;
j--;
}
}
allocate_tickets(answer);
return sum;
}
