#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
long long find_maximum(int k, vector<vector<int>> v){
int n = v.size(), m = v[0].size();
vector<pii> ordem;
for( int i = 0; i < n; i++ ){
for( int j = 0; j < m; j++ ){
ordem.push_back({ v[i][j], i*m + j });
}
}
sort( ordem.begin(), ordem.end() );
vector<int> cont(n);
deque<pii> dq;
for( auto p : ordem ) dq.push_back(p);
vector<vector<int>> resp( n, vector<int>(m, -1));
ll sum_maiores = 0, sum_menores = 0;
multiset<pair<int, int>> smin, smax;
set<int> usados;
for( int i = 0; i < k*n/2; i++ ){
cont[dq.back().second/m]++;
usados.insert(dq.back().second);
sum_maiores += dq.back().first;
smax.insert(dq.back());
dq.pop_back();
}
for( int i = 0; i < k*n/2; i++ ){
cont[dq.front().second/m]++;
usados.insert(dq.front().second);
sum_menores += dq.front().first;
smin.insert(dq.front());
dq.pop_front();
}
for( int i = 0; i < n; i++ ){
if( cont[i] <= k ){
for( int j = 0; j < m; j++ ){
smin.erase({ v[i][j], i*m + j });
smax.erase({ v[i][j], i*m + j });
}
}
}
while( !smin.empty() && !smax.empty() ){
while( !dq.empty() && cont[dq.back().second/m] >= k ) dq.pop_back();
while( !dq.empty() && cont[dq.front().second/m] >= k ) dq.pop_front();
if( smin.empty() ){
auto [val, id] = *smax.begin();
smax.erase(smax.begin());
usados.erase(id);
sum_maiores -= val;
id /= m;
cont[id]--;
if( cont[id] <= k ){
for( int j = 0; j < m; j++ ){
smin.erase({ v[id][j], id*m + j });
smax.erase({ v[id][j], id*m + j });
}
}
sum_maiores += dq.back().first;
cont[dq.back().second/m]++;
usados.insert(dq.back().second);
dq.pop_back();
continue;
}
if( smax.empty() ){
auto [val, id] = *smin.rbegin();
smin.erase(prev(smin.end()));
usados.erase(id);
sum_menores -= val;
id /= m;
cont[id]--;
if( cont[id] <= k ){
for( int j = 0; j < m; j++ ){
smin.erase({ v[id][j], id*m + j});
smax.erase({ v[id][j], id*m + j});
}
}
sum_menores += dq.front().first;
cont[dq.front().second/m]++;
usados.insert(dq.front().second);
dq.pop_front();
continue;
}
if( abs( smin.rbegin()->first - dq.front().first ) >= abs( smax.begin()->first - dq.back().first ) ){
auto [val, id] = *smax.begin();
smax.erase(smax.begin());
usados.erase(id);
sum_maiores -= val;
id /= m;
cont[id]--;
if( cont[id] <= k ){
for( int j = 0; j < m; j++ ){
smin.erase({ v[id][j], id*m + j});
smax.erase({ v[id][j], id*m + j});
}
}
sum_maiores += dq.back().first;
cont[dq.back().second/m]++;
usados.insert(dq.back().second);
dq.pop_back();
continue;
}
else{
auto [val, id] = *smin.rbegin();
smin.erase(prev(smin.end()));
usados.erase(id);
sum_menores -= val;
id /= m;
cont[id]--;
if( cont[id] <= k ){
for( int j = 0; j < m; j++ ){
smin.erase({ v[id][j], id*m + j});
smax.erase({ v[id][j], id*m + j});
}
}
sum_menores += dq.front().first;
cont[dq.front().second/m]++;
usados.insert(dq.front().second);
dq.pop_front();
continue;
}
}
vector<int> vmax[n], vmin[n];
ordem.clear();
for( int x : usados ) ordem.push_back({ v[x/m][x%m], x });
sort( ordem.begin(), ordem.end() );
for( int i = 0; i < k*n/2; i++ ) vmin[ordem[i].second/m].push_back(ordem[i].second);
for( int i = k*n/2; i < k*n; i++ ) vmax[ordem[i].second/m].push_back(ordem[i].second);
for( int i = 0; i < k; i++ ){
int x = 0;
for( int j = 0; j < n; j++ ){
if( vmax[j].size() > vmin[j].size() ){
int id = vmax[j].back(); vmax[j].pop_back();
resp[id/m][id%m] = i;
}
else if( vmax[j].size() < vmin[j].size() ){
int id = vmin[j].back(); vmin[j].pop_back();
resp[id/m][id%m] = i;
}
else{
if( x == 0 ){
int id = vmax[j].back(); vmax[j].pop_back();
resp[id/m][id%m] = i;
}
else{
int id = vmin[j].back(); vmin[j].pop_back();
resp[id/m][id%m] = i;
}
x ^= 1;
}
}
}
allocate_tickets(resp);
return sum_maiores - sum_menores;
}
