import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class tickets {
long find_maximum(int K, int[][] x) {
int N = x.length;
int M = x[0].length;
int S = (N*K)/2;
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] ints, int[] t1) {
return -Integer.compare(-x[ints[0]][ints[1]] - x[ints[0]][M - K + ints[1]], -x[t1[0]][t1[1]] - x[t1[0]][M-K+t1[1]]);
}
});
for (int i = 0; i < N; i++) {
queue.add(new int[]{i, 0});
}
int[] count = new int[N];
for (int i = 0; i < S; i++) {
int[] next = queue.remove();
count[next[0]]++;
if (next[1]+1 < K) {
queue.add(new int[]{next[0], next[1] + 1});
}
}
long res = 0;
int[][] ans = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(ans[i], -1);
}
int k = 0;
for (int id = 0; id < N; id++) {
int bef = k;
if (count[id] == 0) {
for (int c = 1; c <= K; c++) {
ans[id][M-c] = k;
res += x[id][M - c];
k++;
if (k == K) {
k = 0;
}
}
}
else {
for (int a = 0 ; a < count[id]; a++) {
ans[id][a] = k;
res -= x[id][a];
k++;
if (k == K) {
k = 0;
}
}
int c = 1;
for (int i = k; i != bef; ) {
res += x[id][M - c];
ans[id][M-c] = i;
c++;
i++;
if (i == K) {
i = 0;
}
}
}
}
grader.allocate_tickets(ans);
return res;
}
}
