#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long N,M;
vector< tuple<long long,long long,long long,long long> > lst;
vector< pair<long long,long long> > tmp;
long long find_maximum(int k, vector<vector<int>> x) {
N = x.size(), M = x[0].size();
long long ans = 0;
vector< vector<int> > res(N, vector<int>(M,-1));
for (long long i = 0; i < N; ++i) {
tmp.clear();
for (long long j = 0; j < M; ++j) tmp.emplace_back(x[i][j],j);
sort(tmp.begin(),tmp.end());
ans += tmp.back().first;
res[i][tmp.back().second] = 0;
lst.emplace_back(tmp.back().first+tmp.front().first,i,tmp.front().second,tmp.back().second);
}
sort(lst.begin(),lst.end());
for (long long i = 0; i < N/2; ++i) {
long long a,b,c,d; tie(a,b,c,d) = lst[i];
ans -= a, res[b][d] = -1, res[b][c] = 0;
}
allocate_tickets(res);
return ans;
}
