#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
ll find_maximum(int k, vector<vector<int>>a) {
int n=a.size(), m=a[0].size();
if (m==1) {
vector<int> v; forn(i,n) v.pb(a[i][0]);
sort(all(v));
ll ans=0;
forn(i,n/2) ans+=v[i+n/2]-v[i];
vector<vector<int>> z(n,vector<int>(m,0));
allocate_tickets(z);
return ans;
}
int Z=0;for(auto&x:a)for(auto&y:x)Z=max(Z,y);
if (Z<=1) {
vector<int> s(n);
forn(i,n) forn(j,m) s[i]+=a[i][j];
int ans=0;
vector<vector<int>> rans(n,vector<int>(m,-1));
vector<vector<int>> one(n), zero(n);
forn(i,n) forn(j,m) if (a[i][j]) one[i].pb(j); else zero[i].pb(j);
forn(r,k) {
vector<pi> v2;
forn(i,n) v2.pb({s[i],i});
sort(all(v2));
vector<int> para(n);
forn(i,n/2) {
int x=v2[i].s, y=v2[n-1-i].s;
para[x]=y, para[y]=x;
}
vector<int> vis(n);
vector<int> v;
int forced=0;
forn(i,n) {
if (vis[i]) continue;
if (zero[i].size() && one[para[i]].size()) {
continue;
}
if (one[i].size() && zero[para[i]].size()) {
continue;
}
if (zero[i].size() && zero[para[i]].size()) {
int x=zero[i].back(), y=zero[para[i]].back();
zero[i].pop_back(); zero[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=vis[i]=1;
v.pb(0); v.pb(0);
forced--;
continue;
}
if (one[i].size() && one[para[i]].size()) {
int x=one[i].back(), y=one[para[i]].back();
one[i].pop_back(); one[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=vis[i]=1;
v.pb(1); v.pb(1);
--s[i], --s[para[i]];
forced++;
continue;
}
assert(0);
}
forn(i,n) {
if (vis[i]) continue;
vis[i]=1;
if (forced>0 && zero[i].size() && zero[para[i]].size()) {
int x=zero[i].back(), y=zero[para[i]].back();
zero[i].pop_back(); zero[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
v.pb(0); v.pb(0);
--forced;
continue;
}
if (forced<0 && one[i].size() && one[para[i]].size()) {
int x=one[i].back(), y=one[para[i]].back();
one[i].pop_back(); one[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
v.pb(1); v.pb(1);
--s[i], --s[para[i]];
++forced;
continue;
}
if (s[i] <= s[para[i]]) {
if (zero[i].size() && one[para[i]].size()) {
int x=zero[i].back(), y=one[para[i]].back();
zero[i].pop_back(); one[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
--s[para[i]];
v.pb(0); v.pb(1);
continue;
}
if (one[i].size() && zero[para[i]].size()) {
int x=one[i].back(), y=zero[para[i]].back();
one[i].pop_back(); zero[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
--s[i];
v.pb(0); v.pb(1);
continue;
}
} else {
if (one[i].size() && zero[para[i]].size()) {
int x=one[i].back(), y=zero[para[i]].back();
one[i].pop_back(); zero[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
--s[i];
v.pb(0); v.pb(1);
continue;
}
if (zero[i].size() && one[para[i]].size()) {
int x=zero[i].back(), y=one[para[i]].back();
zero[i].pop_back(); one[para[i]].pop_back();
rans[i][x]=r, rans[para[i]][y]=r;
vis[para[i]]=1;
--s[para[i]];
v.pb(0); v.pb(1);
continue;
}
}
assert(0);
}
sort(all(v));
forn(i,n/2) ans+=v[i+n/2]-v[i];
}
allocate_tickets(rans);
return ans;
}
if (k==1) {
vector<int> mn(n), mx(n);
forn(i,n) {
int _mx=0,_mn=0;
forn(j,m) {
if (a[i][j]>a[i][_mx]) _mx=j;
if (a[i][j]<a[i][_mn]) _mn=j;
}
mx[i]=_mx, mn[i]=_mn;
}
ll s=0;
vector<vector<int>> ans(n,vector<int>(m,-1));
forn(i,n) s+=a[i][mx[i]];
forn(i,n) ans[i][mx[i]]=0;
vector<pi> v;
forn(i,n) {
v.pb({a[i][mx[i]]+a[i][mn[i]],i});
}
sort(all(v));
forn(j,n/2) {
int i=v[j].s;
ans[i][mx[i]]=-1;
ans[i][mn[i]]=0;
s-=a[i][mn[i]]+a[i][mx[i]];
}
allocate_tickets(ans);
return s;
}
exit(0);
}
