#include "tickets.h"
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void Forgat(vector<int> &table, int k, int m, int f){
vector<int> temp(table.size());
for(int i = 0; i < m; i++)
{
if(i < m-k){
temp[i] = table[i];
continue;
}
int x = ((i-m+k) - f + k)%k + m - k;
temp[x] = table[i];
}
table = temp;
return;
}
void Forgat2(vector<int> &v, int f)
{
int n = (int)v.size();
vector<int> temp(n);
for(int i = 0; i < n; i++)
temp[(i-f+n)%n] = v[i];
v = temp;
return;
}
long long find_maximum(int k, vector<vector<int>> table) {
int n = (int)table.size(), m = (int)table[0].size();
vector<pair<int, int>> sor;
for(int i = 0; i < n; i++)
for(int j = m-k; j < m; j++)
sor.push_back(make_pair(table[i][j] + table[i][j-m+k], i));
sort(sor.begin(), sor.end());
vector<int> eltol(n, 0);
for(int i = 0; i < (int)sor.size()/2; i++)
eltol[sor[i].second]++;
vector<vector<int>> table2(n, vector<int>(m));
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
table2[i][j] = j;
for(int i = 0; i < n; i++)
Forgat2(table2[i], eltol[i]);
int forg = 0;
for(int i = 0; i < n; i++)
{
Forgat(table2[i], k, m, forg);
forg = (forg+eltol[i])%k;
}
vector<vector<int>> answer(n, vector<int>(m, -1));
for(int i = 0; i < n; i++)
for(int j = m-k; j < m; j++)
answer[i][table2[i][j]] = j-m+k;
long long ret = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < eltol[i]; j++)
ret -= (long long)table[i][j];
for(int j = m - k + eltol[i]; j < m; j++)
ret += (long long)table[i][j];
}
allocate_tickets(answer);
return ret;
}
