//#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));
rep(k, 0, K){
vector<pii> v;
rep(i, 0, N){
v.pb({M - r[i], i});
}
sort(all(v));
rep(x, 0, N / 2){
auto [n, i] = v[x];
t[i][l[i]--] = k;
}
rep(x, N / 2, N){
auto [n, i] = v[x];
t[i][r[i]++] = k;
}
}
allocate_tickets(t);
return ans;
}
