#include "bits/stdc++.h"
#include "tickets.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll N = 3e6 + 5;
const ll LOG = 21;
ll fw[N],fw2[N];
inline void add(ll c,ll u,ll u2){
for(;c<N;c+=c&-c){
fw[c]+=u;
fw2[c]+=u2;
}
}
inline ll query(ll k,ll res=0,ll p=0){
for(ll i=LOG-1;i>=0;i--){
if(fw2[p+(1LL<<i)]<=k){
p+=(1LL<<i);
k-=fw2[p+(1LL<<i)];
res+=fw[p];
}
}
return res;
}
ll find_maximum(int _k, vector<vector<int>> _x){
ll n=sz(_x),m=sz(_x[0]),k=_k;
ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;
vector<vector<int>> ANS(n,vector<int>(m,-1));
for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) ar[i][j] = _x[i-1][j-1];
for(ll i=1;i<=n;i++){
l[i]=1;
r[i]=m;
}
for(ll i=0;i<k;i++){
vector<array<ll,3>> events;
ll mx = -1 , best = -1;
for(ll j=1;j<=n;j++){
events.push_back({ar[j][l[j]],0,j});
events.push_back({ar[j][r[j]],1,j});
}
sort(all(events));
ll sumi = 0, art = n, eks = 0;
for(ll j=1;j<=n;j++) sumi += ar[j][r[j]];
vector<array<ll,2>> zip;
for(ll j=1;j<=n;j++) zip.push_back({ar[j][l[j]]+ar[j][r[j]],j});
sort(all(zip));
zip.erase(unique(all(zip)),zip.end());
auto get_ind = [&](array<ll,2> val){
ll it = lower_bound(all(zip),val) - zip.begin();
return n - it;
};
for(auto x:events){
ll ekle = ar[x[2]][r[x[2]]]+ar[x[2]][l[x[2]]];
if(x[1] == 0){
art--;
sumi -= ekle;
add(get_ind({ekle,x[2]}),ekle,1);
}
else{
eks++;
sumi -= ar[x[2]][l[x[2]]];
add(get_ind({ekle,x[2]}),-ekle,-1);
}
if(art>n/2 || eks>n/2) continue;
ll hm = sumi + query(n/2 - art);
if(hm > mx){
mx = hm;
best = x[0];
}
}
vector<array<ll,2>> best_choice;
ll left = n/2;
for(ll j=1;j<=n;j++){
if(ar[j][r[j]]<best){
ans-=ar[j][l[j]];
ANS[j][l[j]]=i;
l[j]++;
}
else if(ar[j][l[j]]>best){
ans+=ar[j][r[j]];
ANS[j][r[j]]=i;
r[j]--;
left--;
}
else{
ans-=ar[j][l[j]];
best_choice.push_back({ar[j][l[j]]+ar[j][r[j]],j});
}
}
sort(all(best_choice));
if(left>sz(best_choice)) while(1){}
while(left--){
auto T = best_choice.back();
best_choice.pop_back();
ans+=T[0];
ANS[T[1]][r[T[1]]]=i;
r[T[1]]--;
}
while(!best_choice.empty()){
auto T = best_choice.back();
best_choice.pop_back();
ANS[T[1]][l[T[1]]]=i;
l[T[1]]++;
}
}
allocate_tickets(ANS);
return ans;
}
/*void _(){
ll n,m,k;
cin >> n >> m >> k;
ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;
for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin >> ar[i][j];
for(ll i=1;i<=n;i++){
l[i] = 1;
r[i] = m;
}
for(ll i=0;i<k;i++){
vector<array<ll,3>> events;
ll mx = -1 , best = -1;
for(ll j=1;j<=n;j++){
events.push_back({ar[j][l[j]],0,j});
events.push_back({ar[j][r[j]],1,j});
}
sort(all(events));
ll sumi = 0, art = n, eks = 0;
for(ll j=1;j<=n;j++) sumi += ar[j][r[j]];
vector<array<ll,2>> zip;
for(ll j=1;j<=n;j++) zip.push_back({ar[j][l[j]]+ar[j][r[j]],j});
sort(all(zip));
zip.erase(unique(all(zip)),zip.end());
auto get_ind = [&](array<ll,2> val){
ll it = lower_bound(all(zip),val) - zip.begin();
return n - it;
};
for(auto x:events){
ll ekle = ar[x[2]][r[x[2]]]+ar[x[2]][l[x[2]]];
if(x[1] == 0){
art--;
sumi -= ekle;
add(get_ind({ekle,x[2]}),ekle,1);
}
else{
eks++;
sumi -= ar[x[2]][l[x[2]]];
add(get_ind({ekle,x[2]}),-ekle,-1);
}
if(art>n/2 || eks>n/2) continue;
ll hm = sumi + query(n/2 - art);
if(hm > mx){
mx = hm;
best = x[0];
}
}
assert(best!=-1);
vector<array<ll,2>> best_choice;
ll left = n/2;
for(ll j=1;j<=n;j++){
if(ar[j][r[j]]<best){
ans-=ar[j][l[j]];
//cout << "l sec " << j << '\n';
l[j]++;
}
else if(ar[j][l[j]]>best){
ans+=ar[j][r[j]];
r[j]--;
//cout << "r sec " << j << '\n';
left--;
}
else{
ans-=ar[j][l[j]];
best_choice.push_back({ar[j][l[j]]+ar[j][r[j]],j});
}
}
sort(all(best_choice));
while(left--){
auto T = best_choice.back();
best_choice.pop_back();
ans+=T[0];
//cout << "r sec bruh " << T[1] << '\n';
r[T[1]]--;
}
while(!best_choice.empty()){
auto T = best_choice.back();
best_choice.pop_back();
//cout << "l sec " << T[1] << '\n';
l[T[1]]++;
}
//cout << best << ' ' << ans << '\n';
}
cout << ans << '\n';
}
ll32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
ll tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
