#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
if(k == 1) {
long long ans = 0;
vector<vector<int>> build(n, vector<int>(m, -1));
for(int i = 0; i < n; i++)
ans -= x[i][0], build[i][0] = 0;
vector<pair<int,int>> opt;
for(int i = 0; i < n; i++)
opt.push_back({x[i].back() + x[i].front(), i});
sort(opt.begin(), opt.end(), greater<pair<int,int>>());
for(int i = 0; i < n/2; i++)
build[opt[i].second].front() = -1, build[opt[i].second].back() = 0, ans += opt[i].first;
allocate_tickets(build);
return ans;
}
if(k == m) {
long long ans = 0;
vector<pair<int,pair<int,int>>> all;
vector<vector<int>> build(n, vector<int>(m, -1));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
all.push_back({x[i][j], {i, j}});
sort(all.begin(), all.end());
vector<vector<int>> rm(n), add(n);
for(int i = 0; i < n*m/2; i++)
rm[all[i].second.first].push_back(all[i].second.second), ans -= all[i].first;
for(int i = n*m/2; i < n*m; i++)
add[all[i].second.first].push_back(all[i].second.second), ans += all[i].first;
vector<vector<bool>> mark(n, vector<bool>(m));
int index = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < (int)rm[i].size(); j++, index = (index+1)%k)
build[i][rm[i][j]] = index, mark[i][index] = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < (int)add[i].size(); j++, index = (index+1)%k) {
while(mark[i][index]) index = (index + 1) % k;
build[i][add[i][j]] = index;
mark[i][index] = 1;
}
}
allocate_tickets(build);
return ans;
}
int mx = 0;
for(auto vetor : x)
for(int sla : vetor)
mx = max(mx, sla);
if(mx <= 1) {
vector<vector<int>> build(n, vector<int>(m, -1));
vector<pair<int,pair<vector<int>, vector<int>>>> pares;
for(int i = 0; i < n; i++) {
vector<int> p, n;
for(int j = 0; j < m; j++)
if(x[i][j]) p.push_back(j);
else n.push_back(j);
pares.push_back({i, {p, n}});
}
for(int round = 0; round < k; round++) {
sort(pares.begin(), pares.end(), [](const auto& a, const auto& b) { return a.second.first.size() > b.second.first.size(); });
for(int i = 0; i < n/2; i++) {
int id = pares[i].first;
bool swp = 0;
if(!pares[i].second.first.size()) swp = 1;
if(swp) swap(pares[i].second.first, pares[i].second.second);
build[id][pares[i].second.first.back()] = round;
pares[i].second.first.pop_back();
if(swp) swap(pares[i].second.first, pares[i].second.second);
}
for(int i = n/2; i < n; i++) {
swap(pares[i].second.first, pares[i].second.second);
int id = pares[i].first;
bool swp = 0;
if(!pares[i].second.first.size()) swp = 1;
if(swp) swap(pares[i].second.first, pares[i].second.second);
build[id][pares[i].second.first.back()] = round;
pares[i].second.first.pop_back();
if(swp) swap(pares[i].second.first, pares[i].second.second);
swap(pares[i].second.first, pares[i].second.second);
}
}
int soma = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(build[i][j] != -1) soma += x[i][j];
allocate_tickets(build);
return min(soma, k*n - soma);
}
return 0;
}
