#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7;
void allocate_tickets(vector<vi> s);
ll find_maximum(int k, vector<vi> x){
int n = x.size(), m = x[0].size(); ll ans = 0;
vector<vi> s(n, vi(m, -1)); vi f(n, 0), r(n, k-1);
vector<pi> p;
for(int i=0; i<n; i++){
for(int j=0; j<k; j++){
ans -= x[i][j];
p.pb({x[i][j] + x[i][m-k+j], i});
}
}
sort(p.begin(), p.end(), greater<pi>());
for(int i=0, tot=n*k/2; i<tot; i++){
ans += p[i].f; f[p[i].s]++; r[p[i].s]--;
}
for(int i=0, cnt=0; i<k; i++, cnt=0){
for(int j=0; j<n; j++){
if(!f[j]) {
s[j][r[j]] = i; r[j]--;
} else if(r[j] == -1) {
s[j][m - f[j]] = i; f[j]--; cnt++;
}
}
for(int j=0; j<n; j++){
if(f[j] && r[j]!=-1){
if(cnt < n/2) { s[j][m - f[j]] = i; f[j]--; cnt++; }
else { s[j][r[j]] = i; r[j]--; }
}
}
}
allocate_tickets(s); return ans;
}
//void allocate_tickets(vector<vi> s){
// for(int i=0; i<s.size(); i++){
// for(int x: s[i]) cout << x << " ";
// cout << endl;
// }
//}
//int main(){
// vector<vi> a = {{5, 9}, {1, 4}, {3, 6}, {2, 7}};
// cout << find_maximum(1, a) << endl;
//}
