/**
* Author: MatijaL
* Time: 2021-01-17 18:15:39
**/
#include <tickets.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1000000005
#define mod 1000000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;
#define limit 1600
ll find_maximum(int k, vector<vector<int>> x){
ll n = x.size();
ll m = x[0].size();
int label[n][m];
memset(label, 0, sizeof label);
//daj minuse
loop(i, n) loop(j, k) label[i][j] = -1;
//povezave
int d = m - k;
vector<pair<int, pll>> v; //par<cost<i, j> >
loop(i, n){
loop(j, k){
v.pb(mp(x[i][j+d] + x[i][j], mp(i, j)));
}
}
sort(all(v));
reverse(all(v));
loop(i, (k*n)/2){
auto e = v[i];
pll c = e.sc;
label[c.fs][c.sc] = 0;
label[c.fs][c.sc+d] = 1;
}
vector<vector<int>> out (n, vector<int>(m, -1));
ll ans = 0;
int K = 0;
loop(color, n){
loop(i, m){
if(label[color][i] != -1) break;
out[color][i] = K;
K++;
K%=k;
ans -= x[color][i];
}
}
assert(K==0);
K = k-1;
loop(color, n){
for(int i = m-1; i>=0; i--){
if(label[color][i] != 1) break;
out[color][i] = K;
K--;
if(K < 0) K+=k;
ans += x[color][i];
}
}
//assert(K==0);
allocate_tickets(out);
return ans;
}
