#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1502
int N,M;
int alc[MAXN][MAXN]; ///0 e nishto, 1 e minus, 2 e plus
int brm[MAXN];
int brp[MAXN];
struct state
{
long long vl;
int ind;
};
bool operator>(state a, state b)
{
return a.vl>b.vl;
}
bool operator<(state a, state b)
{
return a.vl<b.vl;
}
bool cmp(int a, int b)
{
return brp[a]>brp[b];
}
int lst[MAXN];
int fr[MAXN];
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
N=n;
int m = x[0].size();
M=m;
vector<vector<int>> ans;
for (int q=0;q<n;q++)
{
vector<int> ans2;
ans2.resize(m);
for (int w=0;w<m;w++) ans2[w]=-1;
ans.push_back(ans2);
}
long long otg=0;
for (int q=0;q<n;q++)
{
brm[q]=k;
brp[q]=0;
lst[q]=m-1;
fr[q]=0;
for (int w=0;w<k;w++)
{
alc[q][w]=1;
otg-=x[q][w];
}
}
//cout<<otg<<"\n";
priority_queue<state> qu;
for (int q=0;q<n;q++)
{
state cur={x[q][m-1]+x[q][k-1],q};
qu.push(cur);
}
for (int klk=0;klk<(n*k/2);klk++)
{
state tp=qu.top();
qu.pop();
//cout<<tp.vl<<" "<<tp.ind<<"\n";
otg+=tp.vl;
alc[tp.ind][ brm[ tp.ind ] ]=0;
brm[ tp.ind ]--;
alc[ tp.ind ][ m-1-brp[tp.ind] ]=2;
brp[ tp.ind ]++;
//cout<<brm[tp.ind]<<" "<<brp[tp.ind]<<" sa veche\n";
if (brm[tp.ind]==0) continue;
state nxt={ x[tp.ind][brm[tp.ind]-1]+x[tp.ind][ m-1-brp[tp.ind] ] ,tp.ind};
qu.push(nxt);
}
vector<int> zasr;
for (int q=0;q<n;q++) zasr.push_back(q);
for (int cur=0;cur<k;cur++)
{
sort(zasr.begin(),zasr.end(),cmp);
for (int q=0;q<(n/2);q++)
{
ans[ zasr[q] ][ lst[ zasr[q] ] ]=cur;
lst[ zasr[q] ]--;
brp[ zasr[q] ]--;
}
for (int q=(n/2);q<n;q++)
{
ans[ zasr[q] ][ fr[ zasr[q] ] ]=cur;
brm[zasr[q]]--;
fr[ zasr[q] ]++;
}
}
allocate_tickets(ans);
return otg;
}
