#include "tickets.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
using namespace std;
const int SIZE = 1.5e3 + 5;
int answer[SIZE][SIZE];
int mn[SIZE], mx[SIZE];
int type[SIZE][SIZE];
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
answer[i][j] = -1;
}
}
long long sum = 0;
priority_queue<pair<long long, int>> pq;
for (int i = 0; i < n; i++){
for (int j = 0; j < k; j++){
sum -= x[i][j];
}
mn[i] = k - 1;
mx[i] = m;
pq.push({x[i][m - 1] + x[i][k - 1], i});
}
for (int t = n * k / 2; t--;){
pair<long long, int> tmp = pq.top();
pq.pop();
sum += tmp.fs;
mn[tmp.sc]--;
mx[tmp.sc]--;
if(mn[tmp.sc] == -1)
continue;
pq.push({x[tmp.sc][mn[tmp.sc]] + x[tmp.sc][mx[tmp.sc] - 1], tmp.sc});
}
for (int t = 0; t < k; t++){
vector<pair<int, int>> tmp;
for (int i = 0; i < n; i++){
tmp.push_back({mx[i], i});
}
sort(all(tmp));
for (int i = 0; i < n / 2; i++){
answer[tmp[i].sc][tmp[i].fs] = t;
mx[tmp[i].sc]++;
}
for (int i = n / 2; i < n; i++){
answer[tmp[i].sc][mn[tmp[i].sc]] = t;
mn[tmp[i].sc]--;
}
}
vector<vector<int>> ret;
for (int i = 0; i < n; i++) {
vector<int> row;
for (int j = 0; j < m; j++) {
row.push_back(answer[i][j]);
}
ret.push_back(row);
}
allocate_tickets(ret);
return sum;
}
