#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, len[MAXN];
vector<vector<int>> res, A;
bool flag[MAXN];
int k;
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 (!flag[i] && 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;
//cerr << tt << ": " << cnt_mn << sep << cnt_mx << sep << tmp << endl;
if (tmp) 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++;
}
set<pll> pst, nst;
inline void add(int i) {
if (len[i]) pst.insert(pll(A[i][len[i] - 1] + A[i][m - 1 - (k - len[i])], i));
if (len[i] < k) nst.insert(pll(A[i][len[i]] + A[i][m - (k - len[i])], i));
}
inline void remove(int i) {
if (len[i]) pst.erase(pll(A[i][len[i] - 1] + A[i][m - 1 - (k - len[i])], i));
if (len[i] < k) nst.erase(pll(A[i][len[i]] + A[i][m - (k - len[i])], i));
}
ll find_maximum(int k_, vector<vector<int>> A_) {
A = A_;
k = k_;
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];
});
if (k == m) {
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;
}
for (int i = 0; i < n / 2; i++) {
len[i] = k;
add(i);
}
for (int i = n / 2; i < n; i++) {
len[i] = 0;
add(i);
}
while (true) {
vector<pll> nst_f;
vector<pll> pst_f;
if (!nst.empty()) nst_f.push_back(*nst.begin());
if (int(nst.size()) > 1) nst_f.push_back(*next(nst.begin()));
if (!pst.empty()) pst_f.push_back(*pst.rbegin());
if (int(pst.size()) > 1) pst_f.push_back(*next(pst.rbegin()));
pair<int, pll> best = make_pair(-1, make_pair(0, 0));
for (pll e1 : nst_f) {
for (pll e2 : pst_f) {
if (e1.Y == e2.Y) continue;
ll score = e2.X - e1.X;
if (score > best.X)
best = {score, {e2.Y, e1.Y}};
}
}
if (best.X <= 0) break;
int u = best.Y.X, v = best.Y.Y;
remove(u), remove(v);
len[u]--;
len[v]++;
add(u);
add(v);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < len[i]; j++)
mn_vec[i].push_back(j);
for (int j = 0; j < k - len[i]; j++)
mx_vec[i].push_back(m - 1 - j);
}
for (int i = 0; i < k; i++)
get();
allocate_tickets(res);
return fans;
}
