/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
void allocate_tickets (vector <vector <int>> sol);
ll find_maximum (int k, vector <vector <int>> x)
{
int n = (int) x.size();
int m = (int) x[0].size();
int t = m - k;
vector <vector <ll>> sum (n, vector <ll> (m - t + 1));
for(int i = 0; i < n; i++)
{
sum[i][0] = 0;
for(int j = t; j < m; j++)
sum[i][0] += x[i][j];
for(int j = 1; j < m - t + 1; j++)
sum[i][j] = sum[i][j - 1] - x[i][j - 1] - x[i][j + t - 1];
}
vector <int> pos (n);
priority_queue <pair <ll, int>> q;
for(int i = 0; i < n; i++)
{
pos[i] = 0;
if(pos[i] + 1 < (int) sum[i].size())
q.push({sum[i][pos[i] + 1] - sum[i][pos[i]], i});
}
for(int it = 1; it <= k * n / 2; it++)
{
int i = q.top().second;
q.pop();
pos[i]++;
if(pos[i] + 1 < (int) sum[i].size())
q.push({sum[i][pos[i] + 1] - sum[i][pos[i]], i});
}
ll answer = 0;
for(int i = 0; i < n; i++)
answer += sum[i][pos[i]];
vector <int> A (n);
vector <int> B (n);
for(int i = 0; i < n; i++)
{
A[i] = pos[i] - 1;
B[i] = pos[i] + t;
}
vector <vector <int>> sol (n, vector <int> (m, -1));
vector <int> p (n);
for(int i = 0; i < n; i++)
p[i] = i;
for(int step = 0; step < k; step++)
{
sort(p.begin(), p.end(), [&] (const int &i, const int &j)
{
return A[i] > A[j];
});
for(int i = 0; i < n / 2; i++)
{
sol[p[i]][A[p[i]]] = step;
A[p[i]]--;
}
for(int i = n / 2; i < n; i++)
{
sol[p[i]][B[p[i]]] = step;
B[p[i]]++;
}
}
allocate_tickets(sol);
return answer;
}
