#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
using namespace std;
const int N = 1510;
int l[N], r[N];
int cnt[N];
int ans[N][N];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
memset(ans, -1, sizeof ans);
int n = x.size();
int m = x[0].size();
vector<array <int, 3>> valores;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
valores.push_back({x[i][j], i, j});
}
}
sort(valores.begin(), valores.end());
for(int i = 0;i < (n/2)*m;i++){
cnt[valores[i][1]]++;
}
long long res = 0;
int turno = 0;
for(int i = 0;i < n;i++){
r[i] = m-1;
}
for(int i = 0;i < m;i++){
vector <pair <int, int>> contadores;
for(int i = 0;i < n;i++){
contadores.push_back({cnt[i], i});
}
sort(contadores.begin(), contadores.end());
for(int i = 0;i < n/2;i++){
swap(contadores[i].first, contadores[i].second);
ans[contadores[i].first][r[contadores[i].first]] = turno;
res += x[contadores[i].first][r[contadores[i].first]];
r[contadores[i].first]--;
}
for(int i = n/2;i < n;i++){
swap(contadores[i].first, contadores[i].second);
ans[contadores[i].first][l[contadores[i].first]] = turno;
res -= x[contadores[i].first][l[contadores[i].first]];
l[contadores[i].first]++;
cnt[contadores[i].first]--;
}
turno++;
}
vector <vector <int>> answer;
for(int i = 0;i < n;i++){
vector <int> aux;
for(int j = 0;j < m;j++){
aux.push_back(ans[i][j]);
}
answer.push_back(aux);
}
allocate_tickets(answer);
return res;
}
