#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;
}
ll t, n, m, k, a[1505][1505], mark[N], pl[1505], pr[1505], res[1505][1505];
ll cnt[N], visi[1505][1505];
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;
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;
}
pl[i] = k + 1, pr[i] = m;
int tt = m - k + 1;
for(int j=1; j<=k; j++) {
pq1.push({a[i][tt] + a[i][j], i});
tt++;
}
}
for(int i=0; i<k*n/2; i++) {
pll v = pq1.top(); pq1.pop();
pl[v.S] --;
pr[v.S] --;
}
int ptr = 0;
for(int i=1; i<=n; i++) {
// cout<<pl[i]<< " ==> "<<pr[i]<<endl;
for(int j=1; j<pl[i]; j++) {
res[i][j] = ptr;
visi[i][ptr] = 1;
ptr = MOD(ptr + 1, k);
}
}
for(int i=1; i<=n; i++) {
for(int j=pr[i]+1; j<=m; j++) {
while(visi[i][ptr] == 1) ptr = MOD(ptr + 1, k);
visi[i][ptr] = 1;
res[i][j] = ptr;
ptr = MOD(ptr + 1, k);
}
}
// 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);
