#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define add push_back
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())
#define fr first
#define sc second
ll n, m, K;
vector<vector<int>> answer;
vector<int> h, l, r;
ll pl = 0, mi = 0, bo = 0;
void init(int k){
for(int i = 0; i < n; i++){
if(h[i] == 0) {
mi++;
l[i] = 0;
}
else if(h[i] == k) {
pl++;
r[i] = m - 1;
}
else {
bo++;
l[i] = 0;
r[i] = m - 1;
}
}
}
void constructsol(int k){
ll mins = n / 2 - mi, pls = n / 2 - pl;
for(int i = 0; i < n; i++){
if(h[i] == 0){
answer[i][l[i]] = k;
l[i]++;
}
else if(h[i] == k + 1){
answer[i][r[i]] = k;
h[i]--;
r[i]--;
}
else {
if(mins > 0){
answer[i][l[i]] = k;
l[i]++;
mins--;
}
else{
answer[i][r[i]] = k;
h[i]--;
r[i]--;
pls--;
}
}
}
}
long long find_maximum(int k, vector<vector<int>> x) {
n = len(x);
m = len(x[0]);
K = k;
answer.resize(n);
for(int i = 0; i < n; i++){
answer[i].resize(m, -1);
}
vector<pll> v;
h.resize(len(x));
l.resize(len(x));
r.resize(len(x));
long long res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
res -= x[i][j];
v.add({x[i][m - k + j] + x[i][j], i});
}
}
sort(all(v));
// cout << res << endl;
// cout << "----------v---------" << endl;
// for(int i = 0; i < len(v); i++){
// cout << v[i].fr << " " << v[i].sc << endl;
// }
// cout << endl;
for(int i = len(v) - 1; i >= len(v) - (n * k / 2); i--){
h[ v[i].sc ]++;
res += v[i].fr;
}
init(k);
while(k--){
constructsol(k);
}
allocate_tickets(answer);
return res;
}
