#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<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m,-1);
answer.push_back(row);
}
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;
}
}
}
}
