#include "tickets.h"
#include <vector>
#include <queue>
#include <bits/stdc++.h>
using namespace std;
int i,j,n,m,k,sum;
pair<int,int> p;
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
long long find_maximum(int k, vector<vector<int> > x) {
n = x.size();
m = x[0].size();
vector<vector<int> > ans;
vector<int> row(m,-1),f(n),v(n);
for (int i = 0; i < n; i++) ans.push_back(row);
for(i=0; i<n; i++){
for(j=m-k; j<m; j++){
ans[i][j]=-2;
sum+=x[i][j];
}
}
cout<<"--------"<<endl;
for(i=0; i<n; i++){
int y=x[i][0]+x[i][m-k];
pq.push(make_pair(y,i));
}
int y=n*k/2;
while(y--){
int a=pq.top().first; int b=pq.top().second;
if(f[b]>=k){
pq.pop();
a=pq.top().first;
b=pq.top().second;
}
ans[b][m-k+v[b]]=-1; ans[b][v[b]]=-3;
//cout<<m-k+v[b]<<" "<<v[b]<<endl;
//cout<<a<<" "<<b<<endl;
f[b]++; v[b]++;
int c=v[b];
sum-=a;
if(m-k+c!=m-1&&c!=m-1)pq.push(make_pair(x[b][c]+x[b][m-k+c],b));
pq.pop();
}
y=0;
vector<pair<int,int> > a(k);
cout<<sum<<endl;
for(i=0; i<n/2; i++){
y=0;
for(j=0; j<m; j++){
if(ans[i][j]==-2){
ans[i][j]=y;
a[y].first++;
y++;
}
}
}
for(i=n/2; i<n; i++){
y=0;
for(j=0; j<m; j++){
if(ans[i][j]==-3){
a[y].second++;
ans[i][j]=y;
y++;
}
}
}
for(i=0; i<n/2; i++){
int z=y;
for(j=0; j<m; j++){
if(ans[i][j]==-3){
ans[i][j]=z;
a[y].first++;
z++;
}
}
}
for(i=n/2; i<n; i++){
int z=y;
for(j=0; j<m; j++){
if(ans[i][j]==-2){
a[y].second++;
ans[i][j]=z;
z++;
}
}
}
allocate_tickets(ans);
return 1;
}
