#include "tickets.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
ll ans = 0;
vector<vector<int>> vec(n, vector<int>(m));
vector<pii> all;
for(int i=0; i<n; ++i) {
for(int j=m-k; j<m; ++j) {
ans += x[i][j];
vec[i][j-(m-k)] = x[i][j] + x[i][j-(m-k)];
all.push_back(mp(vec[i][j-(m-k)], i));
}
}
sort(all.begin(), all.end());
vector<int> cnt(n), l(n), r(n, m-1);
for(int i=0; i<k*n/2; ++i) {
cnt[all[i].nd]++;
ans -= all[i].st;
}
for(int i=0; i<k; ++i) {
vector<pii> v;
for(int j=0; j<n; ++j) {
v.push_back(mp(cnt[j], j));
}
sort(v.begin(), v.end());
for(int j=0; j<n/2; ++j) {
int it = v[j].nd;
answer[it][r[it]] = i;
r[it]--;
}
for(int j=n/2; j<n; ++j) {
int it = v[j].nd;
answer[it][l[it]] = i;
l[it]++;
cnt[it]--;
}
}
allocate_tickets(answer);
return ans;
}
