#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int) (x).size())
const int MAXN = 1513;
const long long LLINF = 3e18;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, K;
ll grid[MAXN][MAXN];
ll smallest[MAXN][MAXN];
// vl dp[MAXN];//at row i, we have j -s. what's the best we could get?
// vi parent[MAXN];
vpl pq;
vl nums[MAXN];
int mm[MAXN], pp[MAXN];
int mtake[MAXN], ptake[MAXN];
bitset<MAXN> rec;
ll res;
vector<vi> ans;
long long find_maximum(int k, vector<vi> xx)
{
K = k; N = SZ(xx); M = SZ(xx[0]);
ans.resize(N);
FOR(i, 0, N)
{
ans[i].resize(M);
FOR(j, 0, M)
{
ans[i][j] = -1;
grid[i][j] = xx[i][j];
}
FOR(j, 0, M)
{
smallest[i][j + 1] = smallest[i][j] + grid[i][j];
}
}
// dp[0].PB(0);
// FOR(i, 0, N)
// {
// //you're choosing K numbers.
// dp[i + 1].resize(K * (i + 1) + 1);
// parent[i + 1].resize(K * (i + 1) + 1);
// fill(ALL(dp[i + 1]), -LLINF);
// FOR(j, 0, K * i + 1)
// {
// FOR(k, 0, K + 1) //choose k -s
// {
// ll cand = dp[i][j] - smallest[i][k] + biggest[i][K - k];
// if (cand > dp[i + 1][j + k])
// {
// dp[i + 1][j + k] = cand;
// parent[i + 1][j + k] = k;
// // cerr << "PARENT " << i + 1 << ' ' << j + k << " = " << parent[i + 1][j + k] << endl;
// }
// }
// }
// }
FOR(i, 0, N)
{
FOR(j, 0, K)
{
pq.PB({grid[i][M - 1 - j] + grid[i][K - 1 - j], i});
}
res -= smallest[i][K];
mtake[i] = K;
ptake[i] = 0;
}
// cerr << "RES = " << res << endl;
sort(ALL(pq), greater<pll>());
FOR(i, 0, K * (N / 2))
{
int idx = pq[i].se;
mtake[idx]--;
ptake[idx]++;
res += pq[i].fi;
}
// k = K * (N / 2);
// FORD(i, N + 1, 1)
// {
// // cerr << "parent " << i << ' ' << k << " = " << parent[i][k] << endl;
// mtake[i - 1] = parent[i][k];
// k -= parent[i][k];
// }
FOR(i, 0, N)
{
ptake[i] = K - mtake[i];
mm[i] = 0;
pp[i] = M - 1;
// cerr << pp[i] << ' ' << M - 1 - ptake[i] << endl;
// cerr << "ptake " << i << " = " << ptake[i] << endl;
}
FOR(i, 0, K)
{
// cerr << "work " << i << endl;
int minuses = 0, pluses = 0;
FOR(j, 0, N)
{
rec[j] = false;
if (mm[j] == mtake[j])
{
//you have to make it a plus
// cerr << "make " << j << " plus\n";
pluses++;
ans[j][pp[j]] = i;
pp[j]--;
rec[j] = true;
}
else if (pp[j] == M - 1 - ptake[j])
{
// cerr << "make " << j << " mnus\n";
minuses++;
ans[j][mm[j]] = i;
mm[j]++;
rec[j] = true;
}
}
FOR(j, 0, N)
{
if (rec[j]) continue;
if (pluses < N / 2)
{
// cerr << "make " << j << " PLus\n";
pluses++;
ans[j][pp[j]] = i;
pp[j]--;
rec[j] = true;
}
else
{
// cerr << "make " << j << " MNus\n";
minuses++;
ans[j][mm[j]] = i;
mm[j]++;
rec[j] = true;
}
}
//for each row that already got all -s and all +s factor it in.
}
//as long as we make sure to choose enough +s and enough -s we shouldn't need to worry right.
//keep a set of (value, position.)
//i think you always want to take x[0] or x[end] right?
//so if x is 1, then
allocate_tickets(ans);
return res;
}
