#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> lst, mst;
void prp_cmp() {
for (int i = 1; i <= n; i++) {
lst[i] = *min_element(a[i].begin() + 1, a[i].begin() + m + 1);
mst[i] = *max_element(a[i].begin() + 1, a[i].begin() + m + 1);
// cout << i << ": " << lst[i] << " " << mst[i] << '\n';
}
}
arr<arr<pii, N>, N> dp;
void dp_cmp() {
dp[0].fill({-INF, -1});
dp[0][0] = {0, -1};
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= n / 2; c++) {
int tk = (c == 0) ? -INF : dp[i - 1][c - 1].fir + mst[i];
int lv = dp[i - 1][c].fir - lst[i];
dp[i][c] = max(mp(tk, 1), mp(lv, 0));
}
}
}
arr<int, N> dr;
void dr_cmp() {
int i = n, c = n / 2;
while (i != 0) {
dr[i] = dp[i][c].sec;
if (dr[i] == 0) i--;
else i--, c--;
}
// for (int i = 1; i <= n; i++) {
// cout << i << ": " << dr[i] << '\n';
// }
}
void ans_cmp() {
vec<vec<sig>> ass;
for (int i = 1; i <= n; i++) {
int mn = min_element(a[i].begin() + 1, a[i].begin() + m + 1) - a[i].begin();
int mx = max_element(a[i].begin() + 1, a[i].begin() + m + 1) - a[i].begin();
vec<sig> x(m, -1);
if (dr[i] == 0) x[mn - 1] = 0;
else x[mx - 1] = 0;
ass.push_back(x);
}
allocate_tickets(ass);
}
// 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];
prp_cmp();
dp_cmp();
dr_cmp();
ans_cmp();
return dp[n][n / 2].fir;
}
