#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 300 + 10;
const ll inf = 1e18;
int n, m, k, x[maxn][maxn], par[maxn][maxn*maxn], val[maxn];
ll a[maxn][maxn], dp[maxn][maxn*maxn];
int ptl[maxn], ptr[maxn];
bool cmp(int x, int y){
return val[x] > val[y];
}
ll find_maximum(int _k, vector<vector<int>> X) {
n = X.size();
m = X[0].size();
k = _k;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
x[i][j] = X[i][j];
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < k; j++){
a[i][0] -= x[i][j];
}
debug(i, 0, a[i][0]);
for (int j = 1; j <= k; j++){
a[i][j] = a[i][j-1];
// debug(a[i][j], x[i][k-j], x[i][m-j]);
a[i][j] += x[i][k-j];
a[i][j] += x[i][m-j];
debug(i, j, a[i][j]);
}
}
dp[0][0] = 0;
for (int i = 1; i <= n*k/2; i++){
dp[0][i] = -inf;
}
for (int i = 0; i < n; i++){
for (int j = n*k/2; ~j; j--){
dp[i+1][j] = dp[i][j-k] + a[i][0];
par[i+1][j] = 0;
for (int k = 0; k <= j && k <= ::k; k++){
ll tmp = dp[i][j-k] + a[i][k];
if (tmp > dp[i+1][j]){
dp[i+1][j] = tmp;
par[i+1][j] = k;
}
}
// debug(i, k, dp[i+1][j]);
}
}
int i = n, j = n*k/2;
while(i){
ptr[i-1] = m-1;
val[i-1] = par[i][j];
j -= par[i][j];
i--;
}
assert(j == 0);
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++){
ans[i].resize(m, -1);
}
for (int rnd = 0; rnd < k; rnd++){
vector<int> idx;
for (int i = 0; i < n; i++){
idx.push_back(i);
}
sort(idx.begin(), idx.end(), cmp);
for (int i = 0; i < n; i++){
if (i < n/2){
ans[idx[i]][ptr[idx[i]]] = rnd;
ptr[idx[i]]--;
}
else{
ans[idx[i]][ptl[idx[i]]] = rnd;
ptl[idx[i]]++;
}
}
}
allocate_tickets(ans);
return dp[n][n*k/2];
}
