#include <iostream>
#include <vector>
#include <algorithm>
#include "tickets.h"
using namespace std;
int ind[1505];
vector<int> rnd[1505];
long long find_maximum(int k, vector<vector<int>> vec){
long long n = vec.size(), m = vec[0].size(), Ans = 0;
vector<vector<int>> alc(n, vector<int> (m, -1));
for (int it=0;it<k;it++){
long long ans = 0;
vector<pair<int,int>> vc;
for (int i=0;i<n;i++){
ans += vec[i].back();
vc.push_back({-vec[i].back() - vec[i][ind[i]], i});
}
sort(begin(vc), end(vc));
for (int i=n-1;i>=0;i--){
auto [vl, Id] = vc[i];
if (i < n / 2){
alc[Id][vec[Id].size() - 1] = it;
vec[Id].pop_back();
}
else{
alc[Id][ind[Id]++] = it;
ans += vl;
}
}
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++)
if (alc[i][j] != -1)
rnd[alc[i][j]].push_back(vec[i][j]);
}
for (int i=0;i<k;i++){
sort(begin(rnd[i]), end(rnd[i]));
long long ans = 0;
for (int j=0;j<n;j++)
ans += rnd[i][j] * (j < n / 2 ? -1 : +1);
Ans += ans;
}
allocate_tickets(alc);
return Ans;
}
