/**
* 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 median = 0;
struct Card{
int color, pos;
ll num;
ll worth;
Card(int a, int b, ll c){
color = a;
pos = b;
num = c;
worth = abs(num - median);
}
bool operator < (const Card& other){
if(num != other.num) return num < other.num;
if(color != other.color) return color < other.color;
return pos < other.pos;
}
};
bool worth_sort(const Card& a, const Card &b){
if(a.worth!=b.worth) return a.worth > b.worth;
if(a.color!=b.color) return a.color < b.color;
return a.pos < b.pos;
}
ll find_maximum(int K, vector<vector<int>> x){
int n = x.size();
int m = x[0].size();
vector<Card> cards[n];
vector<ll> allNumbers;
vector<vector<int>> out(n, vector<int>(m, -1));
loop(i, n)loop(j, m) cards[i].pb(Card(i, j, x[i][j]));
Card medianCard = Card(0,0,0);
vector<Card> allCards;
loop(color, n)loop(j, m) allCards.pb(cards[color][j]);
sort(all(allCards));
medianCard = allCards[(n*m)/2];
median = medianCard.num;
//printf("MEDIAN is %lld\n", median);
//porihtaj worth
loop(color, n)loop(j, m) cards[color][j].worth = abs(median - cards[color][j].num);
//1. k najboljsih vsake barve
loop(i, n) sort(all(cards[i]), worth_sort);
vector<Card> left[n];
vector<Card> right[n];
vector<int> pointL(n, 0);
vector<int> pointR(n, 0);
//pair<cost, color> right -> subLeft
vector<pll> subLeft;
vector<pll> subRight;
loop(color, n){
int cnt = 0;
int pl = -1;
int pr = -1;
for(auto e : cards[color]){
//printf("Card %d %d %lld\n", e.color, e.pos, e.worth);
if(cnt < K){
cnt++;
if(e < medianCard) left[color].pb(e);
else right[color].pb(e);
pl = left[color].size()-1;
pr = right[color].size()-1;
pointL[color] = pl;
pointR[color] = pr;
}else{
if(e < medianCard){
left[color].pb(e);
//probaj dat iz desne
if(pr >= 0) subLeft.pb(mp(right[color][pr].worth - e.worth, color));
pr--;
}else{
right[color].pb(e);
//daj z leve
if(pl >= 0) subRight.pb(mp(left[color][pl].worth - e.worth, color));
pl--;
}
}
if(pointL[color] > inf) pointL[color] = -1;
if(pointR[color] > inf) pointR[color] = -1;
}
}
/*
printf("Pre-BALANCING\n");
loop(color, n){
printf("Left: ");
loop(i, pointL[color]+1) printf("%lld ", left[color][i].num);
printf("\n");
printf("Right: ");
loop(i, pointR[color]+1) printf("%lld ", right[color][i].num);
printf("\n");
}*/
//2. uravnovesi
/*
loop(color, n) //printf("%d %d\n", pointL[color], pointR[color]);
//printf("SUBSTITUTIONS:\n");
//printf("Left: ");
for(auto e : subLeft) //printf("(%lld %lld) ", e.fs, e.sc);
//printf("\n");
//printf("Right: ");
for(auto e : subRight) //printf("(%lld %lld) ", e.fs, e.sc);
//printf("\n");
*/
int leftCnt = 0;
int rightCnt = 0;
loop(i, n) leftCnt += pointL[i]+1;
loop(i, n) rightCnt += pointR[i]+1;
//printf("left cnt %d | right cnt %d\n", leftCnt, rightCnt);
sort(all(subLeft));
sort(all(subRight));
for(auto e : subLeft){
if(leftCnt >= rightCnt) break;
//printf("one to the left\n");
int curColor = e.sc;
leftCnt++;
rightCnt--;
pointL[curColor]++;
pointR[curColor]--;
}
for(auto e : subRight){
if(rightCnt >= leftCnt) break;
//printf("one to the right\n");
int curColor = e.sc;
rightCnt++;
leftCnt--;
pointR[curColor]++;
pointL[curColor]--;
}
assert(leftCnt == (n*K)/2 and rightCnt == (n*K)/2);
loop(color, n){
assert(pointR[color]+pointL[color]+2 == K);
}
/*
printf("BALANCING\n");
loop(color, n){
printf("Left: ");
loop(i, pointL[color]+1) printf("%lld ", left[color][i].num);
printf("\n");
printf("Right: ");
loop(i, pointR[color]+1) printf("%lld ", right[color][i].num);
printf("\n");
}*/
ll ans = 0;
int k = 0;
loop(color, n)loop(j, (ll)pointL[color]+1){
Card c = left[color][j];
out[c.color][c.pos] = k;
//printf("card %d %d gets %d\n", c.color, c.pos, k);
k++;
k %= K;
ans += c.worth;
}
assert(k == 0);
loop(color, n)loop(j, (ll)pointR[color]+1){
Card c = right[color][j];
out[c.color][c.pos] = k;
k++;
k %= K;
ans += c.worth;
}
assert(k == 0);
//3 lotimo se dela momci
/*
priority_queue<pll> leftstack;
priority_queue<pll> rightstack;
loop(color, n){
leftstack.push(mp(pointL[color]+1, color));
rightstack.push(mp(pointR[color]+1, color));
}
loop(k, K){
//printf("k = %lld assembly: ", k);
int cl = 0;
int cr = 0;
set<int> usedColors;
int it =0;
//nastimaj leve
while(cl < n/2){
pll e = leftstack.top();
leftstack.pop();
int color = e.sc;
int amnt = e.fs;
it++;
if(it > 10) break;
printf("left color %d -> amnt %d\n", color, amnt);
if(usedColors.count(color) or amnt == 0){
leftstack.push(e);
continue;
};
Card c = left[color][amnt-1];
out[c.color][c.pos] = k;
cl++;
ans += c.worth;
usedColors.insert(color);
leftstack.push(mp(color, amnt-1));
//printf("%lld ", c.num);
}
//pa se desne
while(cr < n/2){
pll e = rightstack.top();
rightstack.pop();
int color = e.sc;
int amnt = e.fs;
it++;
if(it > 10) break;
printf("right color %d -> amnt %d\n", color, amnt);
if(usedColors.count(color) or amnt == 0){
rightstack.push(e);
continue;
};
Card c = right[color][amnt-1];
out[c.color][c.pos] = k;
cr++;
ans += c.worth;
usedColors.insert(color);
rightstack.push(mp(color, amnt-1));
//printf("%lld ", c.num);
}
//printf("\n");
assert(cl == n/2 and cr == n/2);
}*/
allocate_tickets(out);
return ans;
}
