#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long INF=1e18;
int zero[1500];
int one[1500];
typedef pair<long long,int> P;
long long find_maximum(int k, vector<vector<int>> v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> answer(n,vector<int>(m));
for(int i=0;i<n;i++) {
zero[i]=k;
one[i]=0;
for(int j=0;j<m;j++) {
answer[i][j]=-1;
}
}
priority_queue<P> pq;
long long ret=0;
for(int i=0;i<n;i++) {
for(int j=0;j<k;j++) {
ret-=v[i][j];
}
for(int j=0;j<k;j++) {
pq.push(P(v[i][j]+v[i][m-k+j],i));
}
}
for(int i=0;i<(n*k)/2;i++) {
zero[pq.top().second]--;
one[pq.top().second]++;
ret+=pq.top().first;
pq.pop();
}
for(int cnt=0;cnt<k;cnt++) {
vector<int> ind;
priority_queue<P> pq;
int pick=n/2;
for(int i=0;i<n;i++) {
if (zero[i]==0) {
ind.push_back(i);
pick--;
continue;
}
if (one[i]==0) {
continue;
}
pq.push(P(one[i]-zero[i],i));
}
for(int i=0;i<pick;i++) {
ind.push_back(pq.top().second);
pq.pop();
}
sort(ind.begin(),ind.end());
for(int i=0;i<n;i++) {
if (binary_search(ind.begin(),ind.end(),i)) {
answer[i][m-one[i]]=cnt;
one[i]--;
}
else {
answer[i][zero[i]-1]=cnt;
zero[i]--;
}
}
}
allocate_tickets(answer);
return ret;
}
