import java.util.Arrays;
import java.util.PriorityQueue;
public class tickets {
long find_maximum(int k, int[][] x) {
int n = x.length;
int m = x[0].length;
int[][] answer = new int[n][m];
for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
long ans = 0;
// i -> m - k + i
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
(int[] a, int[] b) -> {
int col1 = a[0], i1 = a[1];
int col2 = b[0], i2 = b[1];
int s1 = x[col1][i1] + x[col1][m - k + i1];
int s2 = x[col2][i2] + x[col2][m - k + i2];
return s1 != s2 ? s1 - s2 : col1 - col2;
});
for (int i = 0; i < n; i++) {
pq.add(new int[] { i, 0 });
}
int[] until = new int[n];
for (int s = 0; s < k * (n / 2); s++) {
int[] p = pq.poll();
int col = p[0];
int ind = p[1];
until[col]++;
if (ind < k - 1) {
p[1]++;
pq.add(p);
}
}
Tickets[] tickets = new Tickets[n];
for (int i = 0; i < n; i++) {
tickets[i] = new Tickets(i, x[i], until[i] - 1, m - k + until[i]);
}
for (int i = 0; i < k; i++) {
Arrays.sort(tickets, (Tickets a, Tickets b) -> Math.max(b.numMinus(), b.numPlus()) -
Math.max(a.numMinus(), a.numPlus()));
int balance = 0;
int numDaysLeft = k - i;
for (int j = 0; j < n; j++) {
Tickets t = tickets[j];
int col = t.color;
if (t.numMinus() == numDaysLeft) {
int index = t.minusTill;
t.minusTill--;
answer[col][index] = i;
balance--;
} else if (t.numPlus() == numDaysLeft) {
int index = t.plusAfter;
t.plusAfter++;
answer[col][index] = i;
balance++;
} else {
if (t.numMinus() == 0) {
int index = t.plusAfter;
t.plusAfter++;
answer[col][index] = i;
balance++;
} else if (t.numPlus() == 0) {
int index = t.minusTill;
t.minusTill--;
answer[col][index] = i;
balance--;
} else {
if (balance <= 0) {
int index = t.plusAfter;
t.plusAfter++;
answer[col][index] = i;
balance++;
} else {
int index = t.minusTill;
t.minusTill--;
answer[col][index] = i;
balance--;
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < until[i]; j++) {
ans -= x[i][j];
}
for (int j = until[i] + m - k; j < m; j++) {
ans += x[i][j];
}
}
grader.allocate_tickets(answer);
return ans;
}
private class Tickets {
int color;
int[] val;
int minusTill;
int plusAfter;
Tickets(int col, int[] val, int minusTill, int plusAfter) {
this.color = col;
this.val = val;
this.minusTill = minusTill;
this.plusAfter = plusAfter;
}
int numMinus() {
return minusTill + 1;
}
int numPlus() {
return val.length - plusAfter;
}
}
}
