#include<bits/stdc++.h>
#include "tickets.h"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define sz(a) ((int) (a).size())
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define vi vector<int>
#define ull unsigned long long
using namespace std;
const int N = 1 << 21, mod = 1e9 + 7;
int n, m;
vi sp[N][2];
int cp[N];
ll find_maximum(int k, vector<vi>X) {
	vector<pair<ll,int>>pt;
	n = sz(X), m = sz(X[0]);
	L(i, 0, n - 1) {
		L(j, 0, k - 1) {
			pt.pb(X[i][j] + X[i][j + m - k], i);
		}
	}
	sort(pt.begin(), pt.end());
	L(i, 0, k * n / 2 - 1) {
		++cp[pt[i].second];
	}
	ll ns = 0;
	L(i, 0, n - 1) {
		L(j, 0, cp[i] - 1) 
			sp[i][0].pb(j), ns -= X[i][j];
		L(j, m - k + cp[i], m - 1) 
			sp[i][1].pb(j), ns += X[i][j];
	}
	vector<vi>ans(n, vector<int>(m));
	L(i, 0, n - 1) L(j, 0, m - 1) ans[i][j]=-1;
	L(t, 0, k - 1) {
		int cnt[2] = {n / 2, n / 2};
		vi use(n, -1);
		L(i, 0, n - 1) {
			if(!sz(sp[i][0])) {
				use[i] = 1;
				--cnt[1];
			}
			if(!sz(sp[i][1])) {
				use[i] = 0;
				--cnt[0];
			}
		}
		L(i, 0, n - 1) if(use[i] == -1) {
			if(cnt[0]) use[i] = 0;
			else use[i] = 1;
			--cnt[use[i]];
		}
		L(i, 0, n - 1) {
			ans[i][sp[i][use[i]].back()] = t;
			sp[i][use[i]].pop_back();
		}
	}
	// L(i, 0, n - 1) {
	// 	L(j, 0, m - 1) {
	// 		cout << ans[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	allocate_tickets(ans);
	return ns;
}
// int main() {
// 	ios :: sync_with_stdio(false);
// 	cin.tie(0); cout.tie(0);
// 	vector<vi>tank;
// 	tank.pb(vi{0, 2, 5});
// 	tank.pb(vi{1, 1, 3});
// 	find_maximum(2, tank);
// 	// cout << compare_plants(1, 2) << endl;
// 	return 0;
// }