#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*void allocate_tickets(vector<vector<ll>>a){
ll n=a.size();
for(int i=0;i<n;++i){
for(auto&x:a[i])cout<<x<<' ';
cout<<'\n';
}
}*/
#include"tickets.h"
ll find_maximum(int k,vector<vector<int>>x){
ll n=x.size(),m=x[0].size();
vector<vector<int>>ret(n);
for(int i=0;i<n;++i)ret[i].resize(m,-1);
vector<array<ll,2>>isk(n);
for(int i=0;i<n;++i)
isk[i][0]=0,isk[i][1]=m-1;
ll ans=0;
for(int rnd=1;rnd<=k;++rnd){
vector<ll>koji(n,0);
priority_queue<array<ll,2>>pq;
for(int i=0;i<n;++i)
pq.push({x[i][isk[i][1]]-x[i][isk[i][0]],i});
for(int z=0;z<n/2;++z){
koji[pq.top()[1]]^=1;
pq.pop();
}
for(int i=0;i<n;++i){
if(koji[i]){
ans+=x[i][isk[i][1]];
ret[i][isk[i][1]--]=rnd-1;
}
else{
ans-=x[i][isk[i][0]];
ret[i][isk[i][0]++]=rnd-1;
}
}
}
allocate_tickets(ret);
return ans;
}
/*signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout<<find_maximum(1,{{5,9},{1,4},{3,6},{2,7}});
}*/
