#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));
int valor_lim[2]{};
for(int i = 0, aq = 0; i < n; i++) {
for(int j = 0; j < m; j++)
aq += x[i][j];
valor_lim[0] += min(k, aq);
valor_lim[1] += min(k, m - aq);
}
int prioridade = valor_lim[1] < valor_lim[0]; // a prioridade é o que tiver o menor valor limitado
for(int i = 0; i < n; i++) {
int index = 0;
for(int j = 0; j < m && index < k; j++) {
if(x[i][j] == prioridade)
build[i][j] = index++;
}
for(int j = 0; j < m && index < k; j++) {
if(x[i][j] != prioridade)
build[i][j] = index++;
}
}
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;
}
