#include "tickets.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 15e2 + 10;
int n , m , suf[N] , prf[N];
vector<vector<int>> a , answer;
long long find_maximum(int k, vector<vector<int>> x) {
a = x;
n = x.size();
m = x[0].size();
long long ans = 0;
vector <pair<int, int>> all;
for(int i = 0 ; i < n ; i++)
{
prf[i] = k;
for(int j = 0 ; j < k ; j++)
{
all.push_back(make_pair(a[i][m - 1 - j] + a[i][k - 1 - j] , i));
ans -= a[i][j];
//cout << "WTF- " << a[i][j] << endl;
}
}
//cout << ans << endl;
sort(all.rbegin() , all.rend());
for(int i = 0 ; i < n * k / 2 ; i++)
{
ans += all[i].F;
suf[all[i].S]++;
prf[all[i].S]--;
//cout << "WTF+ " << all[i].F << " " << all[i].S << endl;
}
//cout << ans << endl;
for (int i = 0; i < n; i++) {
vector<int> row(m , -1);
answer.push_back(row);
}
int num = 0;
for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < prf[i] ; j++)
{
answer[i][j] = num;
num++;
num %= k;
}
for(int i = n - 1 ; i >= 0 ; i--) for(int j = 0 ; j < suf[i] ; j++)
{
answer[i][m - 1 - j] = num;
num++;
num %= k;
}
allocate_tickets(answer);
return ans;
}
