#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);
for (int i = 0; i < n; i++) {
for (int j = 0; j < pos[i]; j++) {
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;
}
}
// for (int j = 0; j < k-pos[i]; j++) {
// row[j] = apos[0];
// alloc[0]++;
// if (alloc[0] == n/2) {
// alloc[0] = 0;
// apos[0]++;
// }
// }
// for (int j = m-pos[i]; j < m; j++) {
// row[j] = apos[1];
// alloc[1]++;
// if (alloc[1] == n/2) {
// alloc[1] = 0;
// apos[1]++;
// }
// }
answer.push_back(row);
}
allocate_tickets(answer);
return ans;
}
