#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 sub2()
{
}
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 == m)
sub4();
allocate_tickets(answer);
return has;
}
