#include <bits/stdc++.h>
#include "tickets.h"
using ll = long long;
using namespace std;
const int MAXN = 1510;
ll sum[MAXN];
set<ll> num[MAXN];
ll find_maximum(int k, vector<vector<int>> x){
int n = x.size();
int m = x[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
sum[i] += x[i][j];
num[i].insert(j);
}
}
vector<vector<int>> ans;
for(int i=0; i<n; i++){
ans.push_back({});
for(int j=0; j<m; j++) ans[i].push_back(-1);
}
ll ans_max = 0;
for(int i=0; i<k; i++){
set<pair<ll, int>> s;
for(int j=0; j<n; j++) s.insert({x[j][*num[j].rbegin()], j});
int cnt = 0;
while(!s.empty()){
int row = s.rbegin()->second;
s.erase(*s.rbegin());
int id = 0; ll cur = 0;
if(cnt < n / 2){
id = *num[row].rbegin();
cur = x[row][id];
ans_max += cur;
cnt ++;
} else{
id = *num[row].begin();
cur = x[row][id];
ans_max -= cur;
}
num[row].erase(id);
ans[row][id] = i;
sum[row] -= cur;
}
}
allocate_tickets(ans);
return ans_max;
}
