#include <bits/stdc++.h>
#define pb push_back
#define mp(x...) array<int, 2>({x})
#define int int64_t
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int INF = 1e15;
constexpr static int MXN = 1505;
int prefix[MXN][MXN], suffix[MXN][MXN];
void allocate_tickets(vector<vector<int32_t>> s);
int find_maximum(int32_t _k, vector<vector<int32_t>> x)
{
int k = _k;
int n = x.size();
int m = x[0].size();
vector<vector<array<int, 2>>> dp(n+1, vector<array<int,2>>((k*n/2)+1, mp(-INF, -1)));
dp[0][0] = {0, -1};
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= m; j++)
prefix[i][j] = prefix[i][j-1] + x[i][j-1];
for (int j = m-1; j >= 0; j--)
suffix[i][j] = suffix[i][j+1] + x[i][j];
for (int j = 0; j <= k*n/2; j++)
for (int l = 0; l <= min(j, k); l++)
dp[i+1][j] = max(dp[i+1][j], mp(dp[i][j-l][0] - prefix[i][l] + suffix[i][l-k+m], l));
}
debug(dp.size(), n, dp[0].size(), k*n/2);
int current_count = k*n/2;
vector<vector<int32_t>> s(n, vector<int32_t>(m,-1));
vector<array<int, 2>> bounds; // Left right
debug("a");
vector<array<int, 2>> counts; // Small count, n
for (int i = n-1; i >= 0; i--)
{
debug(i);
int current_val = dp[i+1][current_count][1];
counts.pb({current_val, i});
current_count -= current_val;
debug(i, current_count);
bounds.pb({0, m-1});
}
for (int i = 0; i < k; i++)
{
for (int j = n/2; j < n; j++)
{
s[counts[j][1]][bounds[counts[j][1]][1]--] = i;
counts[j][0]--;
}
for (int j = 0; j < n/2; j++)
{
s[counts[j][1]][bounds[counts[j][1]][0]++] = i;
}
sort(counts.begin(), counts.end());
}
debug("b");
allocate_tickets(s);
return dp[n][k*n/2][0];
}
