#include "tickets.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <stdio.h>
using namespace std;
struct update {
int i, j, cost;
bool operator < (update x) {
if (cost == x.cost)
return j < x.j;
return cost < x.cost;
}
};
const int MAX_N = 1500;
int taken[MAX_N][MAX_N];
pair<int, int> tickets[MAX_N][MAX_N];
bool rounds[MAX_N][MAX_N];
vector<update> updates;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
long long cost = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
tickets[i][j] = {x[i][j], j};
sort(tickets[i], tickets[i] + m);
for (int j = 0; j < k; j++) {
cost -= tickets[i][j].first;
taken[i][j] = 1;
}
for (int j = 0; j < k; j++)
updates.push_back({i, j, tickets[i][j].first + tickets[i][m - k + j].first});
}
sort(updates.begin(), updates.end());
reverse(updates.begin(), updates.end());
for (int i = 0; i < n * k / 2; i++) {
auto a = updates[i];
taken[a.i][a.j] = 0;
taken[a.i][m - k + a.j] = 2;
cost += a.cost;
}
vector<vector<int>> alloc(n);
for (int i = 0; i < n; i++) {
alloc[i].resize(m);
for (int j = 0; j < m; j++)
alloc[i][j] = -1;
}
int r = 0;
for (int i = 0; i < n; i++) {
int a = 0;
for (int j = 0; j < m; j++) {
if (taken[i][j] > 0)
a++;
if (taken[i][j] == 1) {
alloc[i][tickets[i][j].second] = r;
rounds[i][r] = true;
r = (r + 1) % k;
}
}
assert(a == k);
}
for (int i = 0; i < n; i++) {
int r = 0;
for (int j = 0; j < m; j++) {
// printf("%d ", taken[i][j]);
if (taken[i][j] == 2) {
while (rounds[i][r])
r++;
rounds[i][r] = true;
alloc[i][tickets[i][j].second] = r;
}
}
// printf("\n");
}
allocate_tickets(alloc);
return cost;
}
