#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
long long find_maximum(int k, vector<vi> x) {
int n = sz(x);
int m = sz(x[0]);
vector<vi> answer;
for(int i = 0; i < n; i++){
answer.pb(vi(m, -1));
}
if(k == 1){
vpl sums;
ll ans = 0;
for(int i = 0; i < n; i++){
sums.pb(mp(x[i][0]+x[i][m-1], i));
ans-=x[i][0];
}
sort(all(sums));
for(int i = n/2; i < n; i++){
ans+=sums[i].f;
answer[sums[i].s][m-1] = 0;
}
for(int i = 0; i < n; i++){
bool chose = 0;
for(int j = 0; j < m; j++){
if(answer[i][j] != -1) chose = 1;
}
if(!chose){
answer[i][0] = 0;
}
}
allocate_tickets(answer);
return ans;
}
for (int i = 0; i < n; i++) {
vi row(m);
for (int j = 0; j < m; j++) {
if (j < k) {
row[j] = j;
} else {
row[j] = -1;
}
}
answer.pb(row);
}
allocate_tickets(answer);
return 1;
}
