#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<long long> bit;
int n;
BIT(int size){
n = size + 5;
bit.assign(n+5,0);
}
void upd(int pos,long long val){
for(++pos;pos < n;pos += pos & -pos){
bit[pos] += val;
}
}
long long get(int pos){
long long ret = 0;
for(++pos;pos > 0;pos -= pos & -pos){
ret += bit[pos];
}
return ret;
}
long long get(int l,int r){
return get(r) - get(l-1);
}
int get_kth(int k){
int pos = 0;
for(int i = 20;i>=0;i--){
if( (pos + (1<<i)) < n && bit[pos + (1<<i)] < k){
k -= bit[pos + (1<<i)];
pos += (1<<i);
}
}
return pos;
}
};
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<int> lp(n,0),rp(n,m-1);
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m,-1);
answer.push_back(row);
}
if(k == 1){
long long ans = 0;
for(int i = 0;i<n;i++){
int lcnt = 0,rcnt = 0;
long long lsum = 0,rsum = 0;
vector<pair<long long,int>> v;
vector<pair<int,int>> lpoints;
vector<pair<int,int>> rpoints;
for(int j = 0;j<n;j++){
if(i == j)continue;
v.push_back({x[j][0] + x[j][m-1],j});
lpoints.push_back({x[j][0],j});
rpoints.push_back({x[j][m-1],j});
rcnt++;
rsum += x[j][m-1];
}
sort(v.rbegin(),v.rend());
sort(lpoints.begin(),lpoints.end());
sort(rpoints.begin(),rpoints.end());
int sz = v.size();
BIT tcnt(sz),ta(sz),tc(sz);
vector<int> ord(n);
int pt1 = 0,pt2 = 0;
for(int j = 0;j<v.size();j++){
ord[v[j].second] = j;
}
int neededl = n/2-1;
int neededr = n/2;
for(int j = 0;j<m;j++){
while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
rcnt--;
rsum -= x[lpoints[pt1].second][m-1];
tcnt.upd(ord[lpoints[pt1].second],1);
ta.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][0]);
tc.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][m-1]);
pt1++;
}
while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
lcnt++;
lsum += x[rpoints[pt2].second][0];
tcnt.upd(ord[rpoints[pt2].second],-1);
ta.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][0]);
tc.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][m-1]);
pt2++;
}
if(lcnt > neededl || rcnt > neededr)continue;
long long nowans = 0;
nowans += rsum - lsum;
nowans -= x[i][j];
int point = tcnt.get_kth(neededr - rcnt);
//cout << point << " " << sz << endl;
//cout << nowans << endl;
nowans += tc.get(0,point);
nowans -= ta.get(point+1,sz-1);
ans = max(ans,nowans);
}
}
for(int i = 0;i<n;i++){
int lcnt = 0,rcnt = 0;
long long lsum = 0,rsum = 0;
vector<pair<long long,int>> v;
vector<pair<int,int>> lpoints;
vector<pair<int,int>> rpoints;
for(int j = 0;j<n;j++){
if(i == j)continue;
v.push_back({x[j][0] + x[j][m-1],j});
lpoints.push_back({x[j][0],j});
rpoints.push_back({x[j][m-1],j});
rcnt++;
rsum += x[j][m-1];
}
sort(v.rbegin(),v.rend());
sort(lpoints.begin(),lpoints.end());
sort(rpoints.begin(),rpoints.end());
int sz = v.size();
BIT tcnt(sz),ta(sz),tc(sz);
vector<int> ord(n);
int pt1 = 0,pt2 = 0;
for(int j = 0;j<v.size();j++){
ord[v[j].second] = j;
}
int neededl = n/2-1;
int neededr = n/2;
for(int j = 0;j<m;j++){
while(pt1 < lpoints.size() && lpoints[pt1].first <= x[i][j]){
rcnt--;
rsum -= x[lpoints[pt1].second][m-1];
tcnt.upd(ord[lpoints[pt1].second],1);
ta.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][0]);
tc.upd(ord[lpoints[pt1].second],x[lpoints[pt1].second][m-1]);
pt1++;
}
while(pt2 < rpoints.size() && rpoints[pt2].first < x[i][j]){
lcnt++;
lsum += x[rpoints[pt2].second][0];
tcnt.upd(ord[rpoints[pt2].second],-1);
ta.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][0]);
tc.upd(ord[rpoints[pt2].second],-x[rpoints[pt2].second][m-1]);
pt2++;
}
if(lcnt > neededl || rcnt > neededr)continue;
long long nowans = 0;
nowans += rsum - lsum;
nowans -= x[i][j];
int point = tcnt.get_kth(neededr - rcnt);
//cout << point << " " << sz << endl;
//cout << nowans << endl;
nowans += tc.get(0,point);
nowans -= ta.get(point+1,sz-1);
if(nowans == ans){
vector<int> use(n,-1);
for(int c = 0;c<=point;c++){
if(tcnt.get(c,c)){
use[v[c].second] = m-1;
}
}
for(int c = point+1;c<=sz-1;c++){
if(tcnt.get(c,c)){
use[v[c].second] = 0;
}
}
for(int c = 0;c<n;c++){
if(i == c){
answer[i][j] = 0;
continue;
}
if(use[c] != -1){
answer[c][use[c]] = 0;
continue;
}
if(x[c][m-1] < x[i][j]){
answer[c][0] = 0;
}
else answer[c][m-1] = 0;
}
allocate_tickets(answer);
return ans;
}
}
}
}
int maxi = 0;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
maxi = max(maxi,x[i][j]);
}
}
if(maxi <= 1){
vector<int> cnt0(n),cnt1(n);
vector<int> lp(n),rp(n);
for(int i = 0;i<n;i++){
lp[i] = 0;
rp[i] = m-1;
for(int j = 0;j<m;j++){
if(x[i][j] == 0){
cnt0[i]++;
}
if(x[i][j] == 1){
cnt1[i]++;
}
}
}
long long ans = 0;
for(int xx = 0;xx<k;xx++){
set<pair<int,int>> s0,s1;
for(int i = 0;i<n;i++){
s0.insert({cnt0[i],i});
s1.insert({cnt1[i],i});
}
int now0 = 0,now1=0;
while(now0 + now1 < n){
int use = (s0.rbegin()->first == 0) || (s1.rbegin()->first != 0 && now0 > now1);
if(use == 0){
now0++;
int point = s0.rbegin()->second;
s0.erase({cnt0[point],point});
s1.erase({cnt1[point],point});
cnt0[point]--;
answer[point][lp[point]++] = xx;
}
if(use == 1){
now1++;
int point = s1.rbegin()->second;
s0.erase({cnt0[point],point});
s1.erase({cnt1[point],point});
cnt1[point]--;
answer[point][rp[point]--] = xx;
}
}
ans += min(now0,now1);
}
allocate_tickets(answer);
return ans;
}
long long tot_ans = 0;
for(int xx = 0;xx<k;xx++){
vector<pair<int,int>> v;
for(int i = 0;i<n;i++){
v.push_back({x[i][lp[i]],i});
}
sort(v.begin(),v.end());
vector<int> now;
for(int i = 0;i<n/2;i++){
answer[v[i].second][lp[v[i].second]] = xx;
now.push_back(x[v[i].second][lp[v[i].second]++]);
}
for(int i = n/2;i<n;i++){
answer[v[i].second][rp[v[i].second]] = xx;
now.push_back(x[v[i].second][rp[v[i].second]--]);
}
sort(now.begin(),now.end());
for(auto u:now){
tot_ans += abs(u - now[n/2]);
}
}
allocate_tickets(answer);
return tot_ans;
}
