import java.util.Arrays;
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];
long[][] bal = new long[n][k + 1];
for (int i = 0; i < n; i++) {
bal[i][0] = 0;
for (int j = m - 1; j >= m - k; j--) {
bal[i][0] += x[i][j];
}
for (int j = 1; j <= k; j++) {
bal[i][j] = bal[i][j - 1] - x[i][m - k + j - 1] - x[i][j - 1];
}
}
int nk = n * k;
long[][] dp = new long[n + 1][2 * nk + 1];
for (int i = 0; i <= 2 * nk; i++) {
dp[n][i] = Long.MIN_VALUE;
}
dp[n][nk] = 0;
for (int pos = n - 1; pos >= 0; pos--) {
for (int b = 0; b <= 2 * nk; b++) {
dp[pos][b] = Long.MIN_VALUE;
for (int y = 0; y <= k; y++) {
int newBal = b + y - (k - y);
if (newBal > 2 * nk || newBal < 0) continue;
if (dp[pos + 1][newBal] != Long.MIN_VALUE) {
dp[pos][b] = Math.max(dp[pos][b], dp[pos + 1][newBal] + bal[pos][y]);
}
}
}
}
for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
int curBal = nk;
long ans1 = 0;
// TicketsWithColors[] plus = new TicketsWithColors[n];
// TicketsWithColors[] minus = new TicketsWithColors[n];
Tickets[] tickets = new Tickets[n];
for (int i = 0; i < n; i++) {
int take = -1;
for (int y = 0; y <= k; y++) {
int b = curBal + y - (k - y);
if (b < 0 || b > 2 * nk) continue;
if (dp[i + 1][b] != Long.MIN_VALUE && dp[i + 1][b] + bal[i][y] == dp[i][curBal]) {
take = y;
break;
}
}
// for (int s = take - 1; s >= 0; s--) {
// answer[i][s] = take - s - 1;
// }
// for (int s = m - 1; s >= m - (k - take); s--) {
// answer[i][s] = take + (m - 1 - s);
// // take - k
// }
tickets[i] = new Tickets(i, x[i], take - 1, m - (k - take));
curBal += take - (k - take);
ans1 += bal[i][take];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int a = 0; a <= tickets[i].minusTill; a++) {
for (int b = tickets[j].plusAfter; b <= m - 1; b++) {
if (tickets[i].val[a] > tickets[j].val[b]) {
return -1;
}
}
}
}
}
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--;
}
}
}
}
}
grader.allocate_tickets(answer);
return ans1;
}
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;
}
}
private class TicketsWithColors {
int color;
int[] val;
int from;
int to;
TicketsWithColors(int color, int[] val, int l, int r) {
this.color = color;
this.val = val;
this.from = l;
this.to = r;
}
}
}
