#include "tickets.h"
#include <vector>
# include <bits/stdc++.h>
using namespace std;
struct elements
{
long long x,y;
long long st;
long long num;
long long fl;
/* elements(long long a,long long b, long long c)
{
fl = 0;
num = -1;
x = a;
y = b;
st = c;
}*/
};
vector<vector<elements>> a;
bool cmp(elements i, elements j)
{
return i.st<j.st;
}
const long long maxn = 1505;
long long gett[maxn],idx=1;
long long minuss[maxn],pluss[maxn];
priority_queue <pair <long long, long long> > q,w;
stack <long long> st;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
long long n = x.size();
long long m = x[0].size();
long long i,j;
//cout<<n<<" "<<m<<endl;
a.resize(n);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
elements p;
//= new elements(i,j,x[i][j]);
p.x= i;
p.y = j;
p.fl = 0;
p.num = -1;
p.st=x[i][j];
a[i].push_back(p);//cout<<"OK"<<endl;
}
}
for(i=0;i<n;i++)
{
sort(a[i].begin(),a[i].end(),cmp);
for(j=0;j<k;j++)
a[i][j].fl = -1;
minuss[i] = k-1;
pluss[i] = m;
q.push({a[i][k-1].st+a[i][m-1].st,i});
}
for(i=0;i<k*n/2;i++)
{
//cout<<"+"<<q.top().first<<" "<<q.top().second<<endl;
long long t = q.top().second;
q.pop();
a[t][minuss[t]].fl = 0;
minuss[t]--;
a[t][pluss[t]-1].fl = 1;
pluss[t]--;
if(minuss[t]>=0)
q.push({a[t][minuss[t]].st+a[t][pluss[t]-1].st,t});
}
/* for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cout<<i<<" : "<< a[i][j].st<< " "<< a[i][j].fl << endl;
}*/
long long ANS = 0;
for(i=0;i<n;i++)
w.push({m-pluss[i],i});
while(!st.empty())st.pop();
for(i=0;i<k;i++)
{
idx++;
for(j=0;j<n/2;j++)
{
long long s =w.top().second;
w.pop();
st.push(s);
gett[s] = idx;
a[s][pluss[s]].num = i;
//cout<<"+"<<a[s][pluss[s]].st<<endl;
ANS+=a[s][pluss[s]].st;
pluss[s]++;
}
for(j=0;j<n;j++)
{
if(gett[j]==idx)continue;
a[j][minuss[j]].num = i;
//cout<<"-"<<a[j][minuss[j]].st;
ANS-=a[j][minuss[j]].st;
minuss[j]--;
}
while(!st.empty())
{
w.push({m-pluss[st.top()],st.top()});
st.pop();
}
}
// cout<<ANS<<endl;
std::vector<std::vector<int>> answer;
for (long long i = 0; i < n; i++) {
std::vector<int> row(m);
for (long long j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
answer[a[i][j].x][a[i][j].y] = a[i][j].num;
}
allocate_tickets(answer);
return ANS;
}
