#include "tickets.h"
#include <bits/stdc++.h>
#define SIZE 1501
using namespace std;
typedef long long ll;
priority_queue<pair<ll, pair<int, int> > > q;
int l[SIZE], r[SIZE];
pair<int, int> arr[SIZE];
ll find_maximum(int K, vector<vector<int> > x)
{
int N=x.size(), M=x[0].size(), col, num, id;
ll sum=0, val;
vector<vector<int> > ret(N);
for (int i=0; i<N; i++) ret[i].resize(M);
for (int i=0; i<N; i++) for (int j=0; j<M; j++) ret[i][j]=-1;
for (int i=0; i<N; i++) for (int j=0; j<K; j++) {
ret[i][j]=0, sum-=x[i][j];
q.push(make_pair(x[i][j]+x[i][M+j-K], make_pair(i, j)));
}
for (int i=0; i<N*K/2; i++) {
val=q.top().first, col=q.top().second.first, num=q.top().second.second;
q.pop();
ret[col][num]=-1, ret[col][M+num-K]=1, sum+=val;
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (ret[i][j]==1) r[i]=M-1, arr[i].first++;
else if (ret[i][j]==0) l[i]=0;
}
arr[i].second=i;
}
for (int i=0; i<K; i++) {
sort(arr, arr+N);
for (int j=0; j<N; j++) {
id=arr[j].second;
if (j<N/2) ret[id][l[id]++]=i;
else ret[id][r[id]--]=i, arr[j].first--;
}
}
allocate_tickets(ret);
return sum;
}
