#include "tickets.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define int long long
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 1505;
int n, m, K, ans, lol[nmax][nmax], ultim[nmax];
vector<int>slava[nmax], marian[nmax];
vector<vector<int32_t>>haida;
void simuleaza(){
haida.resize(n, vector<int32_t>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(lol[i][j] == 0){
haida[i][j] = -1;
}
else if(lol[i][j] == 2){
slava[i].push_back(j);
}
else{
marian[i].push_back(j);
}
}
}
set<pair<int,int>>alic;
for(int i=0;i<K;i++){
alic.clear();
for(int j=0;j<n;j++){
alic.insert({slava[j].size(), j});
}
for(int j=0;j<n;j++) ultim[j] = 0;
auto it = alic.end();
for(int j=1;j<=n/2;j++){
--it;
haida[it->sc][slava[it->sc].back()] = i;
slava[it->sc].pop_back();
ultim[it->sc] = 1;
}
for(int j=0;j<n;j++){
if(ultim[j] != 1){
haida[j][marian[j].back()] = i;
marian[j].pop_back();
}
}
}
}
int find_maximum(int32_t k, vector<vector<int32_t>> x) {
n = x.size();
m = x[0].size();
K = k;
vector<pair<int,pair<int,int>>>xd;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
ans -= (long long)x[i][j];
lol[i][j] = 1;
xd.push_back({x[i][j] + x[i][m-(k-j)], {i, j}});
}
}
sort(all(xd));
reverse(all(xd));
for(int i=0;i<(k*n/2);i++){
auto it = xd[i];
lol[it.sc.fr][it.sc.sc] = 0;
lol[it.sc.fr][m-(k-it.sc.sc)] = 2;
ans += it.fr;
}
simuleaza();
allocate_tickets(haida);
return ans;
}
