#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];
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);
}
}
}
for(int i=0;i<n;i++){
int xd = 0;
for(int j=0;j<m;j++){
if(haida[i][j] == -1) xd++;
}
// cout << xd << '\n';
if(xd != m - K) exit(0);
}
for(int i=0;i<K;i++){
int curr = 0;
for(int j=0;j<n;j++){
if(slava[j].size() && curr < n/2){
++curr;
haida[j][slava[j].back()] = i;
slava[j].pop_back();
}
else{
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;
}
