#include "tickets.h"
#include <algorithm>
#include <vector>
using namespace std;
long long find_maximum(int k, vector<vector<int> > x)
{
int n = x.size();
int m = x[0].size();
long long ans = 0;
vector<pair<int, int> > sum;
for (int i = 0; i < n; i++){
for (int j = 0; j < k; j++){
ans -= x[i][j];
sum.push_back({ x[i][j] + x[i][m - k + j], i });
}
}
sort(sum.rbegin(), sum.rend());
int neg[1500] = { 0, }, pos[1500] = { 0, };
int pop = n * k / 2;
for (int i = 0; i < n; i++) neg[i] = k;
for (int i = 0; i < pop; i++){
ans += sum[i].first;
neg[sum[i].second]--;
pos[sum[i].second]++;
}
vector<vector<int> > alloc(n, vector<int>(m, -1));
int negp[1500] = { 0, }, posp[1500] = { 0, };
for (int i = 0; i < n; i++) posp[i] = m - 1;
for (int r = 0; r < k; r++){
vector<pair<int, int> > use;
for (int i = 0; i < n; i++) use.push_back({ pos[i] - neg[i], i });
sort(use.begin(), use.end());
for (int i = 0; i < n / 2; i++){
int x = use[i].second;
alloc[x][negp[x]++] = r;
neg[x]--;
}
for (int i = n / 2; i < n; i++){
int x = use[i].second;
alloc[x][posp[x]--] = r;
pos[x]--;
}
}
allocate_tickets(alloc);
return ans;
}
