#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
typedef long long ll;
const int MAXN = 1500;
int mx[MAXN], mn[MAXN];
int pai[MAXN][MAXN];
int dp[MAXN][MAXN];
int a[MAXN];
ll find_maximum(int k, vector<vector<int>> x) {
int n = sz(x);
int m = sz(x[0]);
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (x[i][j] > x[i][mx[i]]) mx[i] = j;
if (x[i][j] < x[i][mn[i]]) mn[i] = j;
}
}
ll ans = 0;
vector<bool> ansGotMx(n, false);
for (int i=0; i<n; i++) {
vector<bool> resGotMx(n, false);
vector<bool> got(n, false);
ll res = 0;
int med = x[i][mn[i]];
int availableMn = n/2, availableMx = n/2;
vector<tuple<int, int, int>> ord;
for (int j=0; j<n; j++) {
if (i == j) continue;
if (x[j][mx[j]] < med) {
availableMn--;
res += abs(x[j][mn[j]] - med);
} else if (x[j][mn[j]] > med) {
availableMx--;
res += abs(x[j][mx[j]] - med);
resGotMx[j] = true;
} else {
ord.emplace_back(abs(x[j][mn[j]] - med), j, 0);
ord.emplace_back(abs(x[j][mx[j]] - med), j, 1);
}
}
sort(ord.begin(), ord.end());
for (auto [gain, v, isMx] : ord) {
if (got[v]) continue;
if (gain == 0) {
resGotMx[v] = isMx;
continue;
}
got[v] = true;
if (isMx and availableMx > 0) {
availableMx--;
res += gain;
} else {
availableMn--;
res += abs(x[v][mn[v]] - med);
}
}
if (availableMn < 0 or availableMx < 0) continue;
if (res >= ans) {
ans = res;
swap(ansGotMx, resGotMx);
}
}
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m, -1);
if (ansGotMx[i]) row[mx[i]] = 0;
else row[mn[i]] = 0;
answer.push_back(row);
}
allocate_tickets(answer);
return ans;
}
