#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
struct obj{
ll v,i,j;
bool operator<(const obj &o) const{
return v<o.v;
}
bool operator>(const obj &o) const{
return v>o.v;
}
};
struct pr{
ll i,c;
bool operator<(const pr &o) const{
return c<o.c;
}
};
long long find_maximum(int k, std::vector<std::vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> ans(n,vector<int>(m,-1));
/*if (m == 1){
vector<ll> v;
for(ll i = 0;i<n;i++) {
v.push_back(x[i][0]);
ans[i][0] = 0;
}
allocate_tickets(ans);
sort(v.begin(),v.end());
ll sm = 0;
for(ll i : v) sm += abs(i-v[v.size()/2]);
return sm;
}*/
if (k==1){
vector<deque<pair<ll,ll>>> a(n);
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
a[i].push_back({x[i][j],j});
}
sort(a[i].begin(),a[i].end());
}
ll sm = 0;
for(ll r = 0;r<k;r++){
/*for(ll i = 0;i<n;i++){
cerr << i << ":";
for(auto [v,j] : a[i]){
cerr << " " << v << "," << j;
}
cerr << "\n";
}*/
vector<pair<ll,ll>> ord;
for(ll i = 0;i<n;i++){
ord.push_back({a[i].front().first+a[i].back().first,i});
}
sort(ord.begin(),ord.end());
for(ll i = 0;i<n/2;i++){
auto [v,j] = a[ord[i].second].front();a[ord[i].second].pop_front();
ans[ord[i].second][j] = r;
//cerr << r << " -> " << ord[i].second << " " << j << "\n";
sm -= v;
}
for(ll i = n/2;i<n;i++){
auto [v,j] = a[ord[i].second].back();a[ord[i].second].pop_back();
ans[ord[i].second][j] = r;
//cerr << r << " -> " << ord[i].second << " " << j << "\n";
sm += v;
}
}
allocate_tickets(ans);
return sm;
}
ll sub3 = 1;
for(auto &o : x) for(ll i : o) if(i>1) sub3 = 0;
if(sub3){
ll sm = 0;
vector<vector<obj>> v0(n),v1(n);
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
if(x[i][j])v1[i].push_back({x[i][j],i,j});
else v0[i].push_back({x[i][j],i,j});
}
}
priority_queue<pr> q0,q1;
for(ll i = 0;i<n;i++){
if (v0[i].size()) q0.push({i,(ll)v0[i].size()});
if (v1[i].size()) q1.push({i,(ll)v1[i].size()});
}
for(ll j = 0;j<k;j++){
vector<pr> wait0,wait1;
vector<ll> u(n,0);
ll req = n/2;
while(req&&q1.size()){
sm++;
pr p = q1.top();q1.pop();
p.c = v1[p.i].size();
if (!p.c) continue;
obj o = v1[p.i].back();v1[p.i].pop_back();
p.c--;
ans[o.i][o.j] = j;
u[o.i] = 1;
if(p.c) wait1.push_back(p);
req--;
}
for(ll i = 0;i<n;i++) if(!u[i]){
if (v0[i].size()){
obj o = v0[i].back();v0[i].pop_back();
ans[o.i][o.j] = j;
}else{
sm--;
obj o = v1[i].back();v1[i].pop_back();
ans[o.i][o.j] = j;
}
}
for(pr p : wait0) q0.push(p);
for(pr p : wait1) q1.push(p);
}
allocate_tickets(ans);
return sm;
}
if(k==m){
ll sm = 0;
vector<obj> a;
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
a.push_back({x[i][j],i,j});
}
}
sort(a.begin(),a.end());
ll nm = n*m;
vector<vector<ll>> y(n,vector<ll>(m,1));
for(ll i = 0;i<nm/2;i++){
sm += a.end()[-i-1].v-a[i].v;
y[a[i].i][a[i].j] = 0;
}
{
vector<vector<obj>> v0(n),v1(n);
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
if(y[i][j])v1[i].push_back({y[i][j],i,j});
else v0[i].push_back({y[i][j],i,j});
}
}
priority_queue<pr> q0,q1;
for(ll i = 0;i<n;i++){
if (v0[i].size()) q0.push({i,(ll)v0[i].size()});
if (v1[i].size()) q1.push({i,(ll)v1[i].size()});
}
for(ll j = 0;j<k;j++){
vector<pr> wait0,wait1;
vector<ll> u(n,0);
ll req = n/2;
while(req&&q1.size()){
pr p = q1.top();q1.pop();
p.c = v1[p.i].size();
if (!p.c) continue;
obj o = v1[p.i].back();v1[p.i].pop_back();
p.c--;
ans[o.i][o.j] = j;
u[o.i] = 1;
if(p.c) wait1.push_back(p);
req--;
}
for(ll i = 0;i<n;i++) if(!u[i]){
if (v0[i].size()){
obj o = v0[i].back();v0[i].pop_back();
ans[o.i][o.j] = j;
}else{
obj o = v1[i].back();v1[i].pop_back();
ans[o.i][o.j] = j;
}
}
for(pr p : wait0) q0.push(p);
for(pr p : wait1) q1.push(p);
}
}
allocate_tickets(ans);
return sm;
}
vector<obj> v1,v2; // big small
for(ll i = 0;i<n;i++){
for(ll j = 0;j<m;j++){
v1.push_back({x[i][j],i,j});
}
}
sort(v1.begin(),v1.end());
v2 = v1;
reverse(v2.begin(),v2.end());
vector<vector<obj>> g1(n),g2(n);
ll cnt = n/2*k;
ll sm = 0;
for(ll i = 0;i<cnt;i++){
obj o = v1.back();v1.pop_back();
sm += o.v;
g1[o.i].push_back(o);
}
for(ll i = 0;i<cnt;i++){
obj o = v2.back();v2.pop_back();
sm -= o.v;
g2[o.i].push_back(o);
}
ll bad = 0;
for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k) bad++;
while(bad){
obj o1 = {big,-1,-1}, o2 = {-big,-1,-1};
for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k){
o1 = min(o1,g1[i].back());
o2 = max(o2,g2[i].back());
}
ll d1 = o1.v-v1.back().v;
ll d2 = v2.back().v-o2.v;
if (d1<=d2){
sm -= d1;
g1[o1.i].pop_back();
g1[v1.back().i].push_back(v1.back());
v1.pop_back();
}else{
sm -= d2;
g2[o2.i].pop_back();
g2[v2.back().i].push_back(v2.back());
v2.pop_back();
}
bad = 0;
for(ll i = 0;i<n;i++) if((ll)(g1[i].size()+g2[i].size())>k) bad++;
}
vector<pair<ll,ll>> ord;
for(ll i = 0;i<n;i++) ord.push_back({g1[i].size(),i});
sort(ord.begin(),ord.end(),greater<pair<ll,ll>>());
for(ll j = 0;j<k;j++){
ll c1 = n/2;
for(auto [_,i] : ord){
obj x;
if (g1[i].size()&&c1--){
x = g1[i].back();g1[i].pop_back();
}else{
x = g2[i].back();g2[i].pop_back();
}
ans[i][x.j] = j;
}
}
allocate_tickets(ans);
return sm;
}
