#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1505;
int pos[MAXN];
int n, m, k;
vector<vector<int>> x;
int alloc[2];
int apos[2];
typedef pair<int, int> pii;
int get_val(int i) {
return x[i][k-pos[i]-1]+x[i][m-pos[i]-1];
}
bool mat[MAXN][MAXN];
int cap[MAXN];
int match[2][MAXN];
// bool flow(int cur, bool side = 0) {
// if (side && cap[cur]) {
// cap[cur]--;
// return 1;
// }
// if (side == 0) {
// for (; match[0][cur] < k; match[0][cur]++) {
// if (!mat[cur][match[0][cur]]) continue;
// bool b = flow(match[0][cur], 1);
// if (b) {
// mat[cur][match[0][cur]] ^= 1;
// return 1;
// }
// }
// return 0;
// }
// if (side == 1) {
// for (; match[1][cur] < n; match[1][cur]++) {
// if (mat[match[1][cur]][cur]) continue;
// bool b = flow(match[1][cur], 0);
// if (b) {
// mat[match[1][cur]][cur] ^= 1;
// return 1;
// }
// }
// return 0;
// }
// assert(false);
// }
ll find_maximum(int K, vector<vector<int>> X) {
k = K;
x = X;
ll ans = 0;
n = x.size();
m = x[0].size();
priority_queue<pii> pq;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans -= x[i][j];
}
pq.push(pii(get_val(i), i));
}
for (int _ = 0; _ < n*k/2; _++) {
pii tp = pq.top(); pq.pop();
ans += tp.first;
pos[tp.second]++;
if (pos[tp.second] < k) pq.push(pii(get_val(tp.second), tp.second));
}
fill(cap, cap+k, n/2);
// for (int i = 0; i < n; i++) fill(mat[i], mat[i]+k, 1);
int p = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < pos[i]; j++) {
mat[i][p++] = 1;
p %= k;
// bool b = flow(i);
// if (!b) exit(0);
// assert(b);
}
}
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m, -1);
int a = 0, b = m-pos[i];
for (int j = 0; j < k; j++) {
if (!mat[i][j]) {
assert(a < k-pos[i]);
row[a++] = j;
}
else {
assert(b < m);
row[b++] = j;
}
}
answer.push_back(row);
}
allocate_tickets(answer);
return ans;
}
