#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const int MAXN = 1500 + 10;
vector<int> mn_vec[MAXN], mx_vec[MAXN];
ll fans = 0, tt, n, m;
vector<vector<int>> res, A;
bool flag[MAXN];
inline void get() {
int cnt_mx = n / 2, cnt_mn = n / 2;
vector<pll> ans;
memset(flag, false, sizeof flag);
for (int i = 0; i < n; i++) {
if (mn_vec[i].empty() && cnt_mx) {
ans.push_back({i, mx_vec[i].back()});
mx_vec[i].pop_back();
cnt_mx--;
flag[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (mx_vec[i].empty() && cnt_mn) {
ans.push_back({i, mn_vec[i].back()});
mn_vec[i].pop_back();
cnt_mn--;
flag[i] = true;
}
}
for (int i = 0; i < n; i++) {
if (flag[i]) continue;
// bool tmp = false;
// if (!cnt_mn) tmp = true;
// if (cnt_mn && cnt_mx && (mx_vec[i].size() > mn_vec[i].size())) tmp = true;
else if (cnt_mx) ans.push_back({i, mx_vec[i].back()}), mx_vec[i].pop_back(), cnt_mx--;
else ans.push_back({i, mn_vec[i].back()}), mn_vec[i].pop_back(), cnt_mn--;
}
sort(all(ans), [] (const pll& a, const pll& b) {
return A[a.X][a.Y] < A[b.X][b.Y];
});
for (int i = 0; i < n / 2; i++)
fans -= A[ans[i].X][ans[i].Y];
for (int i = n / 2; i < n; i++)
fans += A[ans[i].X][ans[i].Y];
for (auto [x, y] : ans) {
res[x][y] = tt;
// cerr << x << "," << y << sep;
}
// cerr << endl;
// debug(fans)
tt++;
}
ll find_maximum(int k, vector<vector<int>> A_) {
A = A_;
n = A.size();
m = A[0].size();
res.resize(n);
for (auto& e : res) {
e.resize(m);
for (int& x : e)
x = -1;
}
vector<pll> vec;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
vec.push_back({i, j});
sort(all(vec), [] (const pll& a, const pll& b) {
return A[a.X][a.Y] < A[b.X][b.Y];
});
int s = n * m;
for (int i = 0; i < s / 2; i++)
mn_vec[vec[i].X].push_back(vec[i].Y);
for (int i = s / 2; i < s; i++)
mx_vec[vec[i].X].push_back(vec[i].Y);
for (int i = 0; i < k; i++)
get();
allocate_tickets(res);
return fans;
}
