#include<tickets.h>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;
// void allocate_tickets( std::vector<std::vector<int>> _x);
long long find_maximum(int k, vector<vector<int>> d){
ll ans = 0;
int n = d.size(), m = d[0].size();
vector<vector<int>> A(n, vector<int>(m, -1));
vector<array<ll, 2>> a;
set<array<int, 4>> big, small;
vector<int> H(n), L(n), LS(n);
for(int i = 0; i < n; ++i){
H[i] = k;
for(int j = m - k; j < m; ++j){
ans += d[i][j];
a.pb({-(d[i][j] + d[i][j - (m - k)]), i});
}
}
sort(all(a), greater<array<ll, 2>>());
for(int i = 0; i < n*k/2; ++i){
ans += a[i][0];
H[a[i][1]]--;
}
for(int i = 0; i < n; ++i) L[i] = k - H[i];
for(int i = 0; i < n; ++i) LS[i] = 1;
for(int i = 0; i < n; ++i){
if(H[i] > 0)
big.insert({-H[i], d[i][m - H[i]], i, m - H[i]});
if(L[i] > 0)
small.insert({-L[i], d[i][0], i, 0});
}
for(int turn = 0; turn < k; ++turn){
vector<bool> used(n);
set<array<int, 4>> bt, st;
int c = 0;
for(auto x: big){
if(used[x[2]] || c == n / 2){
bt.insert(x);
continue;
}
used[x[2]] = 1;
A[x[2]][x[3]] = turn;
H[x[2]]--;
c++;
if(H[x[2]] > 0)
bt.insert({-H[x[2]], d[x[2]][m - H[x[2]]], x[2], m - H[x[2]]});
}
c = 0;
for(auto x: small){
if(used[x[2]] || c == n / 2){
st.insert(x);
continue;
}
used[x[2]] = 1;
A[x[2]][x[3]] = turn;
L[x[2]]--;
c++;
if(L[x[2]] > 0){
st.insert({-L[x[2]], d[x[2]][LS[x[2]]], x[2], LS[x[2]]});
LS[x[2]]++;
}
}
big.swap(bt);
small.swap(st);
}en;
allocate_tickets(A);
return ans;
}
