#include <bits/stdc++.h>
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std;
typedef long long ll;
ll find_maximum(int k, vector<vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> answer;
ll res=0;
if(m==1){
vector<ll> a;
for(ll i=0;i<n;i++){
a.pb(x[i][0]);
}
sort(a.begin(),a.end());
for(ll i=0;i<n;i++){
res+=abs(a[i]-a[n/2]);
}
for(ll i=0;i<n;i++){
answer.pb({0});
}
}
else if(k==1){
for(ll i=0;i<n;i++){
vector<int> d;
for(ll j=0;j<m;j++){
d.pb(-1);
}
answer.pb(d);
}
res=-1;
ll ind=0;
ll l[n],f[n];
vector<array<ll,3>> c;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
c.pb({x[i][j],i,j});
}
l[i]=x[i][m-1];
f[i]=x[i][0];
}
sort(c.begin(),c.end());
set<pair<ll,ll>> s1,s2;
ll cnt=0;
ll sum1=0,sum2=0,sum3=0;
ll sz=(ll)c.size();
for(ll i=0;i<n;i++){
sum3+=l[i];
}
for(ll i=0;i<sz;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==m-1){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
sum2-=p.first;
}
else{
s2.erase(p);
}
}
ll res1=0;
if((ll)s1.size()==n/2-cnt){
ll sum=sum2;
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
if((ll)s2.size()!=0){
sum-=p.first;
p=*(--s2.end());
sum+=p.first;
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
else{
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
if(c[i][2]==0){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
sum2+=nw.first;
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
sum2-=p.first;
sum2+=nw.first;
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==m-1){
cnt++;
sum1+=f[c[i][1]];
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
sum2-=h.first;
}
sum3-=l[c[i][1]];
}
if(res1>res){
res=res1;
ind=i;
}
}
cnt=0;
s1.clear();
s2.clear();
for(ll i=0;i<=ind;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==m-1){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
}
else{
s2.erase(p);
}
}
if(i==ind){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
for(auto x:s1){
if(x.second!=c[i][1]){
answer[x.second][0]=0;
}
}
if(s1.find(p)!=s1.end()){
if((ll)s2.size()==0){
continue;
}
p=*(--s2.end());
answer[p.second][0]=0;
}
for(ll j=0;j<n;j++){
if(j==c[i][1]){
answer[c[i][1]][c[i][2]]=0;
continue;
}
if(answer[j][0]==-1 && answer[j][m-1]==-1){
answer[j][m-1]=0;
}
}
break;
}
if(c[i][2]==0){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==m-1){
answer[c[i][1]][0]=0;
cnt++;
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
}
}
}
}
else{
for(ll i=0;i<n;i++){
vector<int> d;
for(ll j=0;j<m;j++){
d.pb(-1);
}
answer.pb(d);
}
int cnt[n][2],ind[n][2];
for(int i=0;i<n;i++){
cnt[i][0]=cnt[i][1]=0;
ind[i][0]=0;
ind[i][1]=m-1;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cnt[i][x[i][j]]++;
}
}
for(int i=0;i<k;i++){
int cnt0,cnt1,h0,h1;
cnt0=cnt1=0;
for(int j=0;j<n;j++){
if(cnt[j][0]>0){
cnt0++;
}
if(cnt[j][1]>0){
cnt1++;
}
}
if(cnt0>=n/2 && cnt1>=n/2){
h0=n/2;
h1=n/2;
if(n%2){
if(cnt1>cnt0){
h0++;
}
else{
h1++;
}
}
}
else if(cnt0<cnt1){
h0=cnt0;
h1=n-h0;
}
else{
h1=cnt1;
h0=n-h1;
}
res+=min(h0,h1);
for(int j=0;j<n;j++){
if((cnt[j][0]>0)+(cnt[j][1]>0)==1){
if(cnt[j][0]){
h0--;
answer[j][ind[j][0]]=i;
ind[j][0]++;
cnt[j][0]--;
}
if(cnt[j][1]){
h1--;
answer[j][ind[j][1]]=i;
ind[j][1]--;
cnt[j][1]--;
}
}
}
for(int j=0;j<n;j++){
if((cnt[j][0]>0)+(cnt[j][1]>0)==2){
if(h0){
h0--;
answer[j][ind[j][0]]=i;
ind[j][0]++;
cnt[j][0]--;
}
else if(h1){
h1--;
answer[j][ind[j][1]]=i;
ind[j][1]--;
cnt[j][1]--;
}
}
}
}
}
allocate_tickets(answer);
return res;
}
