#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long m_allocate_tickets(vector<vector<int>> answer,vector<vector<int>> x){
allocate_tickets(answer);
// find k;
int N = answer.size();
int k = 0;
for(auto &i:answer[0]) k = max(i+1,k);
vector<vector<int>> cards(k);
for(int i = 0;i < N;i++){
for(int j = 0;j < answer[0].size();j++){
if(answer[i][j] != -1) cards[answer[i][j]].push_back(x[i][j]);
}
}
long long ans = 0;
for(auto v:cards) {
sort(v.begin(),v.end());
for(int i = 0;i < N;i++){
if(i < N/2){
ans -= v[i];
}else{
ans += v[i];
}
}
}
return ans;
}
#define inf (long long)(1e15)
long long find_maximum(int k, vector<vector<int>> x) {
vector<vector<int>> cx = x;
int N = x.size();
int M = x[0].size();
vector<vector<int>> backtrack(N,vector<int>(N*k/2+1));// dp[round][take+];
vector<long long> dp(N*k/2+1,-inf);
dp[0] = 0;
for(int i = 0;i < N;i++){
vector<long long> take(k+1);
for(int j = 0;j < k;j++){
take[0] -= x[i][j];
}
for(int j = 1;j <= k;j++){
take[j] = take[j-1]+x[i][M-j]+x[i][k-j];
}
vector<long long> ndp(N*k/2+1);
for(int j = 0;j <= N*k/2;j++){
backtrack[i][j] = 0;
ndp[j] = dp[j]+take[0];
for(int tk = 1;tk <= k;tk++){
if(j-tk < 0) break;
if(dp[j-tk]+take[tk] > ndp[j]){
ndp[j] = dp[j-tk]+take[tk];
backtrack[i][j] = tk;
}
}
}
swap(dp,ndp);
}
vector<int> ones(N,0);
x = vector<vector<int>>(N,vector<int>(M,0));
{
int cur = N*k/2;
for(int i = N-1;i >= 0;i--){
ones[i] = backtrack[i][cur];
for(int d = 0;d < ones[i];d++){
x[i][M-d-1] = 1;
}
cur -= backtrack[i][cur];
}
}
// for(auto &i:ones) cout << i << " ";
vector<vector<int>> answer(N,vector<int>(M,-1));
vector<int> fpt(N,0);
vector<int> bpt(N,M-1);
for(int ck = 0;ck < k;ck++){
// for(auto &i:ones) cout << i << " ";cout << endl;
vector<pair<int,int>> colors;// cone,idx;
for(int i = 0;i < N;i++){
colors.push_back({ones[i],i});
}
sort(colors.begin(),colors.end());
for(int i = 0;i < N;i++){
// cout << type[i];
auto [cone,cidx] = colors[i];
if(i < N/2){// take zero
answer[cidx][fpt[cidx]] = ck;
ones[cidx] -= x[cidx][fpt[cidx]];
fpt[cidx]++;
}else{// take one
answer[cidx][bpt[cidx]] = ck;
ones[cidx] -= x[cidx][bpt[cidx]];
bpt[cidx]--;
}
}
}
return m_allocate_tickets(answer,cx);
}
