#include "tickets.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(s) s.begin(), s.end()
using namespace std;
const int nmax = 1505;
int n, m;
long long ans;
vector<int>indx[nmax][2];
long long find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
vector<pair<int,pair<int,int>>>arr;
vector<vector<int>>kek(n, vector<int>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
arr.push_back({x[i][j], {i, j}});
}
}
sort(all(arr));
for(int i=0;i<(n*m/2);i++){
ans -= (long long)arr[i].fr;
indx[arr[i].sc.fr][0].push_back(arr[i].sc.sc);
}
for(int i=(n*m/2);i<n*m;i++){
ans += (long long)arr[i].fr;
indx[arr[i].sc.fr][1].push_back(arr[i].sc.sc);
}
for(int i=1;i<=m;i++){
int lol = 0;
for(int j=1;j<=n;j++){
if(indx[j-1][0].size() < indx[j-1][1].size()){
auto it = indx[j - 1][1].back();
indx[j - 1][1].pop_back();
kek[j-1][it] = i - 1;
}
else if(indx[j-1][0].size() > indx[j-1][1].size()){
auto it = indx[j - 1][0].back();
indx[j - 1][0].pop_back();
kek[j - 1][it] = i - 1;
}
else{
if(lol){
lol = 0;
auto it = indx[j - 1][1].back();
indx[j - 1][1].pop_back();
kek[j-1][it] = i - 1;
}
else{
lol = 1;
auto it = indx[j - 1][0].back();
indx[j - 1][0].pop_back();
kek[j - 1][it] = i - 1;
}
}
}
}
allocate_tickets(kek);
return ans;
}
