#include "tickets.h"
#include <vector>
#include <algorithm>
#define ll long long
#define For(i, n) for(int i = 0; i < n; i++)
#define NEK 1000000000
#define vec vector
#define pii pair<int, int>
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
if(m == 1){
vec<int> a;
For(i, n){
a.push_back(x[i][0]);
}
sort(a.begin(), a.end());
ll sum = 0;
vec<vec<int>> odp(n, vec<int>(1, 0));
For(i, n/2){
sum -= a[i];
sum += a[i+n/2];
}
allocate_tickets(odp);
return sum;
}
vec<pii> s;
ll sum = 0;
vec<int> bt, bt2;
vec<vec<int>> odp(n, vec<int>(m,-1));
For(i, n){
int mi = 0, ma = 0;
For(j, x[i].size()){
if(x[i][j] < x[i][mi]){
mi = j;
}
if(x[i][j] > x[i][ma]){
ma = j;
}
}
odp[i][ma] = 0;
bt.push_back(ma);
bt2.push_back(mi);
s.push_back({x[i][mi] + x[i][ma], i});
sum += x[i][ma];
}
sort(s.begin(), s.end());
For(i, n/2){
odp[s[i].second][bt[s[i].second]] = -1;
odp[s[i].second][bt2[s[i].second]] = 0;
sum -= s[i].first;
}
allocate_tickets(odp);
return sum;
}
