#include "tickets.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int inf = 1e9;
/*
4 3 2
0 3 8
1 8 10
1 6 8
6 6 7
*/
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
ll ans = -1, M = -1;
vector<int> lor_(n);
auto check = [&](int mid){
ll res = 0;
ar<int, 2> all {};
vector<ar<int, 2>> diff;
vector<int> lor(n);
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
int l = j + m - k;
if(x[i][l] < mid){
res += (mid - x[i][j]);
lor[i]++; all[0]++;
continue;
}
if(mid < x[i][j]){
res += (x[i][l] - mid);
all[1]++;
continue;
}
lor[i]++;
all[0]++;
res += mid - x[i][j];
diff.push_back({-(mid - x[i][j]) + (x[i][l] - mid), i});
}
}
if(all[1] * 2 > n * k || (all[1] + (int)diff.size()) * 2 < n * k) return;
sort(diff.begin(), diff.end());
while(all[1] * 2 < n * k){
int i = diff.back()[1]; //, j = diff.back()[1] % m;
res += diff.back()[0];
diff.pop_back();
lor[i]--;
all[1]++;
}
if(all[1] * 2 != n * k) assert(false);
if(res > ans){
ans = res;
M = mid;
lor_ = lor;
}
};
auto get = [&](vector<int>& lor){
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<vector<int>> used(n, vector<int>(m));
vector<int> l(n), r(n);
for(int i=0;i<n;i++){
for(int j=0;j<lor[i];j++) used[i][j] = 1;
for(int j=m-(k - lor[i]);j<m;j++) used[i][j] = 1;
l[i] = 0, r[i] = m - 1;
}
for(int c=0;c<k;c++){
ar<int, 2> all {};
queue<int> q;
for(int i=0;i<n;i++){
while(!used[i][l[i]]) l[i]++;
while(!used[i][r[i]]) r[i]--;
if(r[i] < lor[i]){
ans[i][l[i]] = c;
l[i]++; all[0]++;
} else if(lor[i] <= l[i]){
ans[i][r[i]] = c;
r[i]--; all[1]++;
} else {
ans[i][l[i]] = c;
l[i]++, all[0]++;
q.push(i);
}
}
assert(all[1] * 2 <= n);
while(!q.empty() && all[1] * 2 < n){
int i = q.front(); q.pop();
all[1]++;
ans[i][--l[i]] = -1;
ans[i][r[i]--] = c;
}
assert(all[1] * 2 == n);
}
return ans;
};
vector<int> tot;
for(int i=0;i<n;i++) tot.insert(tot.end(), x[i].begin(), x[i].end());
sort(tot.begin(), tot.end());
tot.erase(unique(tot.begin(), tot.end()), tot.end());
ll res = 0;
vector<ar<int, 2>> q;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
int l = j + m - k;
q.push_back({x[i][j], i * m + j});
q.push_back({x[i][l] + 1, -i * m - j - 1});
//~ cout<<x[i][j]<<" "<<x[i][l]<<"\n";
res += x[i][l];
}
}
sort(q.begin(), q.end());
multiset<int> L, R;
ll mx = 0;
int l_ = 0, r_ = n * k, h = n * k / 2;
auto norm = [&](){
while((int)R.size() > max(0, h - r_)){
mx -= (*R.begin());
L.insert(*R.begin());
R.erase(R.begin());
}
while((int)R.size() < max(0, h - r_) && !L.empty()){
mx += (*--L.end());
R.insert(*--L.end());
L.erase(--L.end());
}
};
auto add = [&](int x){
R.insert(x);
mx += x;
L.insert(*R.begin());
mx -= (*R.begin());
R.erase(R.begin());
};
auto del = [&](int x){
if(L.count(x)){
L.erase(L.find(x));
} else {
R.erase(R.find(x));
mx -= x;
}
};
//~ cout<<"here"<<endl;
//~ cout<<res<<endl;
int j = 0;
for(auto mid : tot){
while(j < (int)q.size() && q[j][0] <= mid){
if(q[j][1] >= 0){
int i = q[j][1] / m, j_ = q[j][1] % m;
int l = m + j_ - k;
res -= x[i][l] + x[i][j_];
add(x[i][j_] + x[i][l]);
r_--;
} else {
int i = (-q[j][1] - 1) / m, j_ = (-q[j][1] - 1) % m;
int l = m + j_ - k;
del(x[i][j_] + x[i][l]);
l_++;
}
norm();
j++;
}
//~ cout<<mid<<" "<<l_<<" "<<r_<<" "<<h<<" "<<ans<<" "<<res<<" "<<mx<<"\n";
if(l_ <= h && r_ <= h){
if(ans < res + mx){
ans = res + mx;
M = mid;
}
}
}
assert(~M);
//~ cout<<M<<endl;
ans = -1;
check(M);
allocate_tickets(get(lor_));
return ans;
}
