#include "tickets.h"
#include "bits/stdc++.h"
#define SZ 1505
using namespace std;
long long ans = 0;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<pair<int, int>>> xsorted (n, vector<pair<int, int>>(m));
vector<vector<int>> temp (n, vector<int>(m, -1));
vector<vector<int>> temp2 (n, vector<int>(m, -1));
vector<vector<int>> answer (n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
xsorted[i][j] = {x[i][j], j};
sort(xsorted[i].begin(), xsorted[i].end());
for (int j = 0; j < k; j++)
temp[i][j] = 0;
}
vector<pair<int, pair<int, int>>> v;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans -= xsorted[i][j].first;
v.push_back({xsorted[i][m-k+j].first + xsorted[i][j].first, {i, j}});
}
}
sort(v.begin(), v.end());
for (int i = (int)v.size()-1; i >= (int)v.size() - k*n/2; i--) {
ans += v[i].first;
//cout << "i: " << i << " " << v[i].first << " " << ans << "\n";
temp[v[i].second.first][v[i].second.second] = -1;
temp[v[i].second.first][v[i].second.second+m-k] = 1;
}
set<pair<int, int>> sizes;
for (int i = 0; i < k; i++)
sizes.insert({0, i});
for (int i = 0; i < n; i++) {
vector<int> small;
for (int j = 0; j < m; j++) {
if (temp[i][j] == 0)
small.push_back(j);
}
//fill in small rounds
set<int> s; for (int j = 0; j < k; j++) s.insert(j);
vector<pair<int, int>> rem;
for (int j : small) {
int round = (*sizes.begin()).second;
temp2[i][j] = round;
s.erase(round);
rem.push_back(*sizes.begin());
sizes.erase(sizes.begin());
}
//reset sizes
for (auto p : rem) {
if (p.first+1 < n/2)
sizes.insert({p.first+1, p.second});
}
//fill in large rounds
for (int j = 0; j < m; j++) {
if (temp[i][j] == 1) {
temp2[i][j] = *s.begin();
s.erase(s.begin());
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
answer[i][xsorted[i][j].second] = temp2[i][j];
}
allocate_tickets(answer);
return ans;
}
