#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sig signed
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
#define mp make_pair
const int N = 1505, M = 1505, INF = 1e18;
int n, m, k;
arr<arr<int, M>, N> a;
arr<int, N> zr, on;
void intl() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0) zr[i]++;
else on[i]++;
}
}
}
arr<arr<vec<int>, 2>, N> upd;
int upd_cmp() {
int ans = 0;
for (int r = 1; r <= k; r++) {
vec<pii> ord;
for (int i = 1; i <= n; i++) ord.push_back({on[i], i});
sort(ord.begin(), ord.end());
for (int i = 1; i <= n; i++) {
pii x = ord[i - 1];
if (on[x.sec] == 0 || (zr[x.sec] != 0 && i <= n / 2)) {
zr[x.sec]--;
upd[x.sec][0].push_back(r);
} else {
on[x.sec]--;
upd[x.sec][1].push_back(r);
ans += (i <= n / 2) ? -1 : +1;
}
}
}
return ans;
}
arr<arr<int, M>, N> ass;
void ass_cmp() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] == 0 && upd[i][0].size())
ass[i][j] = upd[i][0].back(), upd[i][0].pop_back();
if (a[i][j] == 1 && upd[i][1].size())
ass[i][j] = upd[i][1].back(), upd[i][1].pop_back();
}
}
}
// Return indices 0-indexed
int find_maximum(sig _k, vec<vec<sig>> _a) {
n = _a.size(), m = _a[0].size(), k = _k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = _a[i - 1][j - 1];
intl();
int ans = upd_cmp();
// for (int i = 1; i <= n; i++) {
// for (int j : upd[i][0]) cout << i << " 0 " << j << '\n';
// for (int j : upd[i][1]) cout << i << " 1 " << j << '\n';
// }
ass_cmp();
vec<vec<sig>> x;
for (int i = 1; i <= n; i++) {
vec<sig> y;
for (int j = 1; j <= m; j++) y.push_back(ass[i][j] - 1);
x.push_back(y);
}
allocate_tickets(x);
return ans;
}
