//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void allocate_tickets(vector<vector<int>> _d);
struct Ticket{
ll val; int x, y;
bool operator<(const Ticket& oth) const{
return val < oth.val;
}
};
long long find_maximum(int K, vector<vector<int>> a){
int N = SZ(a), M = SZ(a[0]);
vector<int> l(N), r(N);
ll ans = 0;
vector<Ticket> ch;
rep(i, 0, N){
per(j, K - 1, 0){
ans -= a[i][j];
ch.pb({+a[i][j] + a[i][M+j-K], i, j});
}
l[i] = K - 1, r[i] = M;
}
sort(all(ch));
int cnt = K * N / 2;
while(cnt--){
auto [val, x, y] = ch.back();
ch.pop_back();
ans += val;
--l[x], --r[x];
}
vector<vector<int>> t(N, vector<int>(M, -1));
vector<int> p(N, M - 1);
rep(k, 0, K){
vector<pii> v1, v2;
rep(i, 0, N){
if(p[i] >= r[i]) v1.pb({a[i][p[i]], i});
if(l[i] >= 0) v2.pb({a[i][l[i]], i});
}
sort(all(v1));
sort(all(v2));
vector<bool> used(N, false);
int cnt = N / 2;
for(auto [n, i] : v1){
if(cnt && !used[i]){
used[i] = true;
t[i][p[i]--] = k;
--cnt;
}
}
for(auto [n, i] : v2){
if(!used[i]){
used[i] = true;
t[i][l[i]--] = k;
}
}
}
allocate_tickets(t);
return ans;
}
