#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long best[1501], ans;
vector<pair<long long, long long>> x2[1501], arr;
vector<int> zeros[1501], ones[1501];
int one_cnt[1501];
void calc(vector<int> v) {
sort(v.begin(), v.end());
for(auto i: v)
ans+=abs(i-v[v.size()/2]);
}
long long find_maximum(int k, vector<vector<int>> x) {
long long n = x.size();
long long m = x[0].size();
vector<vector<int>> answer(n,vector<int>(m,-1));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!x[i][j])
zeros[i].push_back(j);
else
ones[i].push_back(j), one_cnt[i]++;
for(int i = 0; i < k; i++) {
vector<pair<int, int>> arr;
for(int j = 0; j < n; j++)
arr.push_back({one_cnt[j], j});
sort(arr.begin(), arr.end());
int one = 0, zero = 0;
for(int j = 0; j < n; j++) {
if(one_cnt[j]) one++;
if(one_cnt[j]!=m-i) zero++;
}
int noz=n/2,noo=n/2;
if(one<n/2)
noo=one,noz=n-noo;
if(zero<n/2)
noz=zero,noo=n-noz;
vector<int> val;
for (int j = 0; j < zero; j++) {
val.push_back(0);
int color = arr[j].second;
vector<int> x = zeros[color];
answer[color][x.back()] = i;
zeros[color].pop_back();
}
for (int j = 0; j < one; j++) {
val.push_back(1);
int color = arr[n - j - 1].second;
answer[color][ones[color].back()] = i;
ones[color].pop_back();
one_cnt[color]--;
}
calc(val);
}
allocate_tickets(answer);
return ans;
}
