#include "tickets.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppp=pair<pii,pii>;
using ppi=pair<int,ppp>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n=x.size(),m=x[0].size();
vector<vector<int>> t(n,vector<int>(m,-1));
priority_queue<ppi,vector<ppi>,greater<ppi>> pq;
ll ans=0;
for(int i=0;i<n;i++) {
for(int j=m-1,cnt=0;cnt<k;cnt++,j--) {
ans+=x[i][j]; t[i][j]=1;
int temp=x[i][j]+x[i][k-cnt-1];
pq.push({temp,{{i,j},{i,k-cnt-1}}});
}
}
int cntt=k*n/2;
vector<tuple<int,int,int>> ar0,ar1; //i,j,type
while(cntt--) {
ppi cur=pq.top(); pq.pop();
ans-=cur.first;
pii p1=cur.second.first; pii p2=cur.second.second;
t[p1.first][p1.second]=-1;
t[p2.first][p2.second]=0;
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(t[i][j]==0) ar0.push_back(tie(i,j,t[i][j]));
else if(t[i][j]==1) ar1.push_back(tie(i,j,t[i][j]));
}
}
set<int> unused[n];
for(int i=0;i<n;i++) {
for(int j=0;j<k;j++) unused[i].insert(j);
}
vector<int> cnt(k,0);
vector<vector<int>> s(n,vector<int>(m,-1));
sort(all(ar0),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
return get<1>(l)<get<1>(r);
});
sort(all(ar1),[&](const tuple<int,int,int> &l,const tuple<int,int,int> &r) {
return get<1>(l)<get<1>(r);
});
for(auto e:ar1) {
int i,j,type; tie(i,j,type)=e;
if(!type) assert(false);
int select=-1;
//debug("idx",i);
//for(auto f:unused[i]) debug(f);
for(auto f:unused[i]) {
if(cnt[f]<n/2) {
select=f; break;
}
}
assert(select!=-1);
cnt[select]++; s[i][j]=select; unused[i].erase(select);
}
for(auto e:ar0) {
int i,j,type; tie(i,j,type)=e;
if(type) assert(false);
int select=-1;
for(auto f:unused[i]) {
if(cnt[f]<n) {
select=f; break;
}
}
assert(select!=-1);
cnt[select]++; s[i][j]=select; unused[i].erase(select);
}
allocate_tickets(s);
return ans;
}
