#include "tickets.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair <ll, ll>
#define piii pair <ll, pii>
#define pb push_back
using namespace std;
const int N = 2005;
ll ans, sign[N][N];
set <ll> neg[N],pos[N];
vector < piii > v;
bool cmp(int a, int b) {
return neg[a].size() > neg[b].size();
}
long long find_maximum(int k, vector< vector<int> > x) {
int n = x.size();
int m = x[0].size();
vector< vector <int> > answ;
answ = vector < vector <int> > (n, vector <int> (m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans -= x[i][j];
sign[i][j] = -1; // neg
v.pb({x[i][j] + x[i][m - (k - j)], {i, j}});
}
}
sort(v.rbegin(),v.rend());
for (int i = 0; i < (k * n) / 2; i++) {
int xi = v[i].s.f; int xj = v[i].s.s;
ans += v[i].f; sign[xi][xj] = 0; sign[xi][m - (k - xj)] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (sign[i][j] == -1) {
neg[i].insert(j);
} else if (sign[i][j] == 1) pos[i].insert(j);
}
}
vector <int> id;
for (int i = 0; i < n; i++) {
id.pb(i);
}
for (int i = 1; i <= k; i++) {
sort(id.begin(), id.end(), cmp);
int cnt = 0;
for (int idx : id) {
cnt++;
if (cnt <= n / 2) {
answ[idx][*neg[idx].begin()] = i - 1;
neg[idx].erase(neg[idx].begin());
} else {
answ[idx][*pos[idx].begin()] = i - 1;
pos[idx].erase(pos[idx].begin());
}
}
}
allocate_tickets(answ);
return ans;
}
