#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));
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);
smax.insert(dq.back());
dq.pop_back();
cont[dq.front().second/m]++;
usados.insert(dq.front().second);
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() || ( !smax.empty() && 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);
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 });
}
}
cont[dq.back().second/m]++;
usados.insert(dq.back().second);
dq.pop_back();
}
else{
auto [val, id] = *smin.rbegin();
smin.erase(prev(smin.end()));
usados.erase(id);
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});
}
}
cont[dq.front().second/m]++;
usados.insert(dq.front().second);
dq.pop_front();
}
}
vector<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() );
ll sum = 0;
for( int i = 0; i < k*n/2; i++ ) vmin[ordem[i].second/m].push_back(ordem[i].second), sum -= ordem[i].first;
for( int i = k*n/2; i < k*n; i++ ) vmax[ordem[i].second/m].push_back(ordem[i].second),sum += ordem[i].first;
for( int i = 0; i < k; i++ ){
vector<pii> aux;
for( int j = 0; j < n; j++ ) aux.push_back({ (int)vmax[j].size() - (int)vmin[j].size(), j });
sort( aux.begin(), aux.end() );
for( int j = 0; j < n/2; j++ ){
int id = vmin[aux[j].second].back(); vmin[aux[j].second].pop_back();
resp[id/m][id%m] = i;
}
for( int j = n/2; j < n; j++ ){
int id = vmax[aux[j].second].back(); vmax[aux[j].second].pop_back();
resp[id/m][id%m] = i;
}
}
allocate_tickets(resp);
return sum;
}
