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++) {
long sumSuffix = 0;
for (int j = m - 1; j >= m - k; j--) {
sumSuffix += x[i][j];
}
bal[i][0] = sumSuffix;
for (int j = 1; j <= k; j++) {
sumSuffix -= x[i][m - k + j - 1];
bal[i][j] = -x[i][j - 1] + sumSuffix;
}
}
int mk = m * k;
long[][] dp = new long[n + 1][2 * mk + 1];
for (int i = 0; i <= 2 * mk; i++) {
dp[n][i] = Long.MIN_VALUE;
}
dp[n][mk] = 0;
for (int pos = n - 1; pos >= 0; pos--) {
for (int b = 0; b <= 2 * mk; b++) {
dp[pos][b] = Long.MIN_VALUE;
for (int y = 0; y <= k; y++) {
int newBal = b - mk + y - (k - y);
if (Math.abs(newBal) > mk) continue;
if (dp[pos + 1][newBal + mk] != Long.MIN_VALUE) {
dp[pos][b] = Math.max(dp[pos][b], dp[pos + 1][newBal + mk] + bal[pos][y]);
}
}
}
}
long ans = 0;
for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
int curBal = 0;
for (int i = n - 1; i >= 0; i--) {
int take = -1;
for (int y = 0; y <= k; y++) {
int newBal = curBal + y - (k - y);
if (Math.abs(newBal) > mk) continue;
if (dp[i + 1][newBal + mk] != Long.MIN_VALUE && dp[i + 1][newBal + mk] + bal[i][y] == dp[i][curBal + mk]) {
take = y;
break;
}
}
for (int s = 0; s < take; s++) {
answer[i][s] = s;
}
for (int s = m - 1; s >= m - (k - take); s++) {
answer[i][s] = s - (m - k);
}
curBal = curBal + take - (k - take);
}
// for (int a = 0; a < k; a++) {
// for (int i = 0; i < n; i++) {
// int col = t[i].color;
// if (i < n / 2) {
// answer[col][t[i].from] = a;
// ans -= t[i].val[t[i].from];
// t[i].from++;
// } else {
// answer[col][t[i].to] = a;
// ans += t[i].val[t[i].to];
// t[i].to--;
// }
// }
// }
grader.allocate_tickets(answer);
return ans;
}
// private class TicketsWithColors {
// int color;
// int[] val;
// int from;
// int to;
//
// TicketsWithColors(int color, int[] val) {
// this.color = color;
// this.val = val;
// this.from = 0;
// this.to = val.length - 1;
// }
// }
// long find_maximum(int k, int[][] x) {
// int n = x.length;
// int m = x[0].length;
// int[][] answer = new int[n][m];
// TicketsWithColors[] t = new TicketsWithColors[n];
// for (int i = 0; i < n; i++) {
// t[i] = new TicketsWithColors(i, x[i]);
// }
// long ans = 0;
// for (int i = 0; i < n; i++) Arrays.fill(answer[i], -1);
// for (int a = 0; a < k; a++) {
// Arrays.sort(t, (t1, t2) ->
// t1.val[t1.from] + t1.val[t1.to] - t2.val[t2.from] - t2.val[t2.to]);
// for (int i = 0; i < n; i++) {
// int col = t[i].color;
// if (i < n / 2) {
// answer[col][t[i].from] = a;
// ans -= t[i].val[t[i].from];
// t[i].from++;
// } else {
// answer[col][t[i].to] = a;
// ans += t[i].val[t[i].to];
// t[i].to--;
// }
// }
// }
// //grader.allocate_tickets(answer);
// return ans;
// }
}
