#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "tickets.h"
ll find_maximum(int K, vector<vector<int>> a_given) {
int N = a_given.size();
int M = a_given[0].size();
vector<vi> a(N, vi(M, 0));
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
a[i][j] = a_given[i][j];
}
}
vi ans(N, -1);
ll maximum = -1;
for (int i = 0; i < N; i++) {
// try with minimum
vi ans1(N, -1);
ans1[0] = 0;
ll total1 = 0;
for (int j = 1; j < N; j++) {
if (abs(a[j][0] - a[i][0]) < abs(a[j][M - 1] - a[i][0])) {
ans1[j] = M - 1;
total1 += abs(a[j][M - 1] - a[i][0]);
}
else {
ans1[j] = 0;
total1 += abs(a[j][0] - a[i][0]);
}
}
vi ans2(N, -1);
ans2[0] = M - 1;
ll total2 = 0;
for (int j = 1; j < N; j++) {
if (abs(a[j][0] - a[i][M - 1]) < abs(a[j][M - 1] - a[i][M - 1])) {
ans2[j] = M - 1;
total2 += abs(a[j][M - 1] - a[i][M - 1]);
}
else {
ans2[j] = 0;
total2 += abs(a[j][0] - a[i][M - 1]);
}
}
if (total1 > maximum) {
ans = ans1;
maximum = total1;
}
if (total2 > maximum) {
ans = ans2;
maximum = total2;
}
}
vector<vector<int>> answer(N, vector<int>(M, -1));
for (int i = 0; i < N; i++) {
answer[i][ans[i]] = 0;
}
allocate_tickets(answer);
return maximum;
}
