#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 sum[1505][1505], dp[303][303*303];
vector<ll> hlp[N];
long long find_maximum(int _k, vector<vector<int>> d) {
k = _k, n = size(d), m = size(d[0]);
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);
}
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);
