#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
/*#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")*/
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e18;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
bool comp(pll a, pll b)
{
return a.second>b.second;
}
int S,D,mns,pls;
ll cap[2005][2005],nodes,dist[2005],from[2005],l[2005],r[2005],nr1[2005],nr0[2005],maxi[2005];
vector<ll> muchii[2005];
int use[2005];
int flow;
bool sub3;
ll k;
bool byplus(int a,int b)
{
return cap[a][pls]>cap[b][pls];
}
long long find_maximum(int K, std::vector<std::vector<int>> vectoras)
{
k=K;
n = vectoras.size();
m = vectoras[0].size();
sol=vectoras;
v=vectoras;
sub3=1;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
sol[i][j]=-1;
if(v[i][j]>1)
sub3=0;
}
pls=0;
mns=1;
ll ans=0;
multiset<pll> s;
for(int i=0;i<n;i++)
{
l[i]=k-1;
r[i]=m;
cap[i][mns]=k;
cap[i][pls]=0;
for(int j=0;j<k;j++)
ans-=v[i][j];
s.insert({v[i][r[i]-1]+v[i][l[i]],i});
}
for(int pas=0;pas<k*n/2;pas++)
{
auto it=prev(s.end());
int i=(*it).second;
cap[i][mns]--;
cap[i][pls]++;
ans+=v[i][r[i]-1]+v[i][l[i]];
r[i]--;
l[i]--;
s.erase(it);
if(cap[i][mns]>0)
s.insert({v[i][r[i]-1]+v[i][l[i]],i});
}
for(int i=0;i<n;i++)
{
l[i]=0;
r[i]=m-1;
}
for(int pas=0;pas<k;pas++)
{
vector<int> linii;
for(int i=0;i<n;i++)
linii.push_back(i);
sort(linii.begin(),linii.end(),byplus);
for(int z=0;z<n;z++)
{
int i=linii[z];
if(z<n/2)
{
assert(cap[i][pls]>0);
cap[i][pls]--;
sol[i][r[i]]=pas;
r[i]--;
}
else
{
assert(cap[i][mns]>0);
cap[i][mns]--;
sol[i][l[i]]=pas;
l[i]++;
}
}
}
allocate_tickets(sol);
return ans;
}
