// In the name of Allah
#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1500 + 4;
int n, m, k;
vector<vector<int>> ans;
vector<pll> Ax[maxn];
ll A[maxn][maxn], sm[maxn];
int valx[maxn]; ll res = 0;
priority_queue<pll> qu;
vector<int> ls1[maxn], ls2[maxn];
ll find_maximum(int k, vector<vector<int>> Rx) {
n = len(Rx); m = len(Rx[0]);
for (int i = 0; i < n; i++) {
Ax[i].resize(m);
for (int j = 0; j < m; j++) Ax[i][j] = Mp(Rx[i][j], j);
sort(all(Ax[i]));
sm[0] = 0;
for (int j = 0; j < m; j++) sm[j + 1] = sm[j] + Ax[i][j].F;
for (int j = 0; j <= k; j++) {
A[i][j] = (sm[m] - sm[m - j]) - sm[k - j];
}
valx[i] = 0; res += A[i][valx[i]];
if (valx[i] + 1 <= k) {
qu.push(Mp(A[i][valx[i] + 1] - A[i][valx[i]], i));
}
}
int R = (n * k) / 2;
while (R--) {
auto f = qu.top(); qu.pop();
res += f.F;
int i = f.S; valx[i]++;
if (valx[i] + 1 <= k) {
qu.push(Mp(A[i][valx[i] + 1] - A[i][valx[i]], i));
}
}
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m); fill(all(ans[i]), -1);
}
for (int i = 0; i < n; i++) {
int j = valx[i];
for (int r = 0; r < k - j; r++) ls1[i].pb(Ax[i][r].S);
for (int r = m - j; r < m; r++) ls2[i].pb(Ax[i][r].S);
reverse(all(ls1[i]));
}
for (int T = 0; T < k; T++) {
int T1 = n / 2, T2 = n / 2;
for (int i = 0; i < n; i++) {
if (len(ls2[i]) == 0) {
int j = ls1[i].back(); ls1[i].pop_back();
ans[i][j] = T;
T1--;
}
else if (len(ls1[i]) == 0) {
int j = ls2[i].back(); ls2[i].pop_back();
ans[i][j] = T;
T2--;
}
}
for (int i = 0; i < n; i++) {
if (len(ls1[i]) + len(ls2[i]) != k - T) continue;
if (T1 > 0) {
int j = ls1[i].back(); ls1[i].pop_back();
ans[i][j] = T;
T1--;
}
else {
int j = ls2[i].back(); ls2[i].pop_back();
ans[i][j] = T;
T2--;
}
}
}
allocate_tickets(ans);
return res;
}
