#include "tickets.h"
#include <vector>
#include <algorithm>
#define ll long long
#define For(i, n) for(int i = 0; i < n; i++)
#define NEK 1000000000
#define vec vector
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vec<pair<int, pii>> p;
For(i, n){
For(j, m){
p.push_back({x[i][j], {i, j}});
}
}
sort(p.begin(), p.end());
ll sum = 0;
int kolo1 = 0;
vec<vec<int>> velkaci(n);
vec<vec<int>> odp(n, vec<int>(m, -1));
vec<vec<int>> bol(n, vec<int>(k, 0));
For(i, (n*m)/2){
sum += p[i+(n*m)/2].ff;
int ja = p[i+(n*m)/2].ss.ff;
int ja_listok = p[i+(n*m)/2].ss.ss;
velkaci[ja].push_back({ja_listok});
}
For(i, velkaci.size()){
For(j, velkaci[i].size()){
odp[i][velkaci[i][j]] = kolo1;
bol[i][kolo1] = 1;
kolo1++;
if(kolo1 == k) kolo1 -= k;
}
}
vec<int> pos(n, 0);
vec<int> poc(k, (n*m)/2);
For(i, (n*m)/2){
sum -= p[i].ff;
int ja = p[i].ss.ff;
int ja_listok = p[i].ss.ss;
while(bol[ja][pos[ja]] || poc[pos[ja]] == 0) pos[ja]++;
odp[ja][ja_listok] = pos[ja];
poc[pos[ja]]--;
pos[ja]++;
}
allocate_tickets(odp);
return sum;
}
