#include "tickets.h"
#include <vector>
# include <bits/stdc++.h>
using namespace std;
struct elements
{
int x,y;
int st;
int num;
int fl;
/* elements(int a,int b, int 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 int maxn = 1505;
int gett[maxn],idx=1;
int minuss[maxn],pluss[maxn];
priority_queue <pair <int, int> > q,w;
stack <int> st;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int 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++)
{
int t = q.top().second;
q.pop();
a[t][minuss[t]].fl = 0;
minuss[t]--;
a[t][pluss[t]-1].fl = 1;
pluss[t]--;
}
/* for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cout<<i<<" : "<< a[i][j].st<< " "<< a[i][j].fl << endl;
}*/
int 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++)
{
int s =w.top().second;
w.pop();
st.push(s);
gett[s] = idx;
a[s][pluss[s]].num = i;
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;
ANS-=a[j][minuss[j]].num;
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 (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int 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;
}
