#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vv=vector<vector<ll>>;
ll nbSorte,nbDeChaque,nbTour;
vv val,pris;
ll calcRep() {
ll sommeRep=0;
vector<tuple<int,int,int>> listePris;
vector<vector<int>> rep;
for (ll i=0;i<nbSorte;i++) {
rep.push_back({});
for (ll j=0;j<nbDeChaque;j++) {
if (pris[i][j]==1) {
listePris.push_back(make_tuple(val[i][j],i,j));
rep[i].push_back(0);
}
else {
rep[i].push_back(-1);
}
}
}
sort(listePris.begin(),listePris.end());
for (ll i=0;i<(ll)listePris.size();i++) {
if (i<(ll)listePris.size()/2) {
sommeRep-=get<0>(listePris[i]);
}
else {
sommeRep+=get<0>(listePris[i]);
}
rep[get<1>(listePris[i])][get<2>(listePris[i])]=i%nbTour;
}
allocate_tickets(rep);
return sommeRep;
}
ll find_maximum(int k,vector<vector<int>> x) {
for (auto i:x) {
val.push_back({});
for (auto j:i) {
val.back().push_back((ll)j);
}
}
nbTour=k;
nbSorte=val.size();
nbDeChaque=val[0].size();
for (ll i=0;i<nbSorte;i++) {
pris.push_back({});
for (ll j=0;j<nbDeChaque;j++) {
pris.back().push_back(0);
}
}
if (nbTour==nbDeChaque) {
for (ll i=0;i<nbSorte;i++) {
for (ll j=0;j<nbDeChaque;j++) {
pris[i][j]=1;
}
}
}
return calcRep();
}
