#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
ll MOD(ll a, ll mod=Mod) {
a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
ll res = 1;
while(b > 0) {
if(b%2 == 1) res = MOD(res * a, mod);
b /= 2;
a = MOD(a * a, mod);
}
return res;
}
int t, n, m, k, a[1505][1505], mark[N], pl[1505], pr[1505], res[1505][1505];
ll cnt[N];
vector<ll> hlp[N];
long long find_maximum(int _k, vector<vector<int>> d) {
k = _k, n = size(d), m = size(d[0]);
priority_queue<pll> pq1;
priority_queue<pll> pq2;
for(int i=1; i<=n; i++) {
// pl[i] = 1, pr[i] = m;
for(int j=1; j<=m; j++) {
a[i][j] = d[i-1][j-1];
res[i][j] = -1;
}
sort(a[i] + 1, a[i] + m + 1);
if(i <= n / 2) {
pl[i] = k + 1, pr[i] = m;
pq1.push({a[i][pl[i]-1] + a[i][pr[i]], i});
// for(int j=1; j<=k; j++) res[i][j] = j-1;
} else {
pl[i] = 1, pr[i] = m - k;
pq2.push({- a[i][pr[i]+1] - a[i][pl[i]], i});
// for(int j=m-k+1; j<=m; j++) res[i][j] = j-(m-k+1);
}
}
while(pq1.top().F + pq2.top().F > 0) {
pll v1 = pq1.top(), v2 = pq2.top();
pq1.pop(), pq2.pop();
pl[v1.S] --, pr[v1.S] --;
pq1.push({a[v1.S][pl[v1.S]-1] + a[v1.S][pr[v1.S]], v1.S});
pl[v2.S] ++, pr[v2.S] ++;
pq2.push({- a[v2.S][pr[v2.S]+1] - a[v2.S][pl[v2.S]], v2.S});
// int t1 = res[v1.S][pl[v1.S]], t2 = res[v2.S][pr[v2.S]];
// res[v1.S][pl[v1.S]] = -1;
// res[v2.S][pr[v2.S]] = -1;
// res[v2.S][pl[v2.S]-1] = t1;
// res[v1.S][pr[v1.S]+1] = t2;
}
for(int i=1; i<=n; i++) {
// cout<<pl[i]<< " ==> "<<pr[i]<<endl;
vector<pii> perm;
for(int j=0; j<k; j++) {
perm.pb({cnt[j], j});
}
sort(all(perm));
int ptr = 0;
for(int j=pr[i]+1; j<=m; j++) {
cnt[perm[ptr].S] ++;
res[i][j] = perm[ptr++].S;
}
for(int j=1; j<pl[i]; j++) {
cnt[perm[ptr].S] --;
res[i][j] = perm[ptr++].S;
}
}
// for(int i=1; i<=n; i++) {
// for(int j=1; j<pl[i]; j++) res[i][j]
// }
// for(int tc=1; tc<=k; tc ++) {
// vector<pll> vec;
// fill(mark, mark+n+2, 0);
// for(int j=1; j<=n; j++) {
// vec.pb({ -a[j][pl[j]] - a[j][pr[j]], j});
// }
// sort(all(vec));
// reverse(all(vec));
// for(int i=0; i<n/2; i++) {
// mark[vec[i].S] = 1;
// }
// for(int i=1; i<=n; i++) {
// if(mark[i] == 1) {
// res[i][pl[i]] = tc - 1;
// pl[i] ++;
// } else {
// res[i][pr[i]] = tc - 1;
// pr[i] --;
// }
// }
// }
ll ans = 0;
vector<vector<int>> tmp;
for(int i=1; i<=n; i++) {
tmp.pb({});
for(int j=1; j<=m; j++) tmp.back().pb(res[i][j]);
for(int j=1; j<=m; j++) {
if(res[i][j] >= 0) hlp[res[i][j]].pb(a[i][j]);
}
}
allocate_tickets(tmp);
for(int i=0; i<k; i++) {
sort(all(hlp[i]));
ll mid = hlp[i][n/2];
for(auto it : hlp[i]) {
ans += abs(mid - it);
}
}
return ans;
}
// void allocate_tickets( std::vector<std::vector<int>> _x);
