#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 1505;
ll n, m, k, has, B[NN], K[NN], a[NN][NN];
std::vector<std::vector<int>> answer;
std::vector<std::vector<int>> x;
vector<ll> bes[NN], kec[NN];
void sub1()
{
vector<ll> tmp;
for(ll i = 0; i < n; i++)
{
answer[i][0] = 0;
tmp.pb(x[i][0]);
}
sort(tmp.begin(), tmp.end());
for(ll i = 0; i < n; i++)
if(i < (n / 2))
has -= tmp[i];
else
has += tmp[i];
}
void sub4()
{
vector<pair<ll, pair<ll, ll> > >tmp;
for(ll i = 0; i < n; i++)
for(ll j = 0; j < m; j++)
tmp.pb(mp(x[i][j], mp(i, j)));
sort(tmp.begin(), tmp.end());
for(ll i = 0; i < (n * m); i++)
if(i < ((n * m) / 2))
has -= tmp[i].fi;
else
{
a[tmp[i].se.fi][tmp[i].se.se] = 1;
has += tmp[i].fi;
}
for(ll i = 0; i < n; i++)
{
for(ll j = 0; j < m; j++)
{
if(a[i][j])
{
B[i]++;
bes[i].pb(j);
}
else
{
K[i]++;
kec[i].pb(j);
}
}
}
for(ll i = 0; i < k; i++)
{
vector<pair<ll, ll> > z;
for(ll j = 0; j < n; j++)
z.pb(mp(B[j], j));
sort(z.begin(), z.end());
for(ll j = 0; j < n; j++)
{
ll idx = z[j].se;
// continue;
if(j < (n / 2))
{
ll temp = kec[idx].back();
kec[idx].pop_back();
// cout << idx << " " << temp << "K_\n";
answer[idx][temp] = i;
}
else
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
// cout << idx << " " << temp << "B_\n";
answer[idx][temp] = i;
}
}
}
}
void sub3()
{
for(ll i = 0; i < n; i++)
{
for(ll j = 0; j < m; j++)
{
if(x[i][j])
{
B[i]++;
bes[i].pb(j);
}
else
{
K[i]++;
kec[i].pb(j);
}
}
}
for(ll i = 0; i < k; i++)
{
vector<pair<ll, ll> > z;
for(ll j = 0; j < n; j++)
z.pb(mp(B[j], j));
sort(z.begin(), z.end());
for(ll j = 0; j < n; j++)
{
ll idx = z[j].se;
// continue;
if(j < (n / 2))
{
if(kec[idx].empty())
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
has += x[idx][temp];
answer[idx][temp] = i;
}
else
{
ll temp = kec[idx].back();
kec[idx].pop_back();
answer[idx][temp] = i;
}
}
else
{
if(bes[idx].empty())
{
ll temp = kec[idx].back();
kec[idx].pop_back();
answer[idx][temp] = i;
}
else
{
B[idx]--;
ll temp = bes[idx].back();
bes[idx].pop_back();
has += x[idx][temp];
answer[idx][temp] = i;
}
}
}
}
}
ll d[NN][NN];
ll b[NN][NN];
ll depe(ll pos, ll sisa)
{
if(pos == n && sisa == 0)
return 0;
if(sisa < 0 || pos == n)
return -1e18;
if(!b[pos][sisa])
{
b[pos][sisa] = 1;
if(depe(pos + 1, sisa) - x[pos][K[pos]] < depe(pos + 1, sisa - 1) + x[pos][B[pos]])
d[pos][sisa] = depe(pos + 1, sisa - 1) + x[pos][B[pos]];
else
d[pos][sisa] = depe(pos + 1, sisa) - x[pos][K[pos]];
}
return d[pos][sisa];
}
void bt(ll pos, ll sisa)
{
if(pos == n)
return ;
if(depe(pos + 1, sisa) - x[pos][K[pos]] < depe(pos + 1, sisa - 1) + x[pos][B[pos]])
{
answer[pos][B[pos]] = 0;
bt(pos + 1, sisa - 1);
}
else
{
answer[pos][K[pos]] = 0;
bt(pos + 1, sisa);
}
}
void sub2()
{
for(ll i = 0; i < n; i++)
{
vector<pair<ll, ll> > tmp;
for(ll j = 0; j < m; j++)
tmp.pb(mp(x[i][j], j));
sort(tmp.begin(), tmp.end());
K[i] = tmp[0].se;
B[i] = tmp[m - 1].se;
// cout << K[i] << " " << B[i] << "_\n";
}
has = depe(0, n / 2);
bt(0, n / 2);
}
long long find_maximum(int tk, std::vector<std::vector<int>> tx) {
k = tk;
x = tx;
n = x.size();
m = x[0].size();
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
if(m == 1)
sub1();
else
if(k == 1)
sub2();
else
if(k == m)
sub4();
else
sub3();
allocate_tickets(answer);
return has;
}
