//In the name of God
#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 1510;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Mp make_pair
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())
ll cnt[maxn], cn[maxn];
vector<ll> c2[maxn];
bool vis[maxn][maxn];
long long find_maximum(int k, vector<vector<int>> a) {
ll n = Sz(a);
ll m = Sz(a[0]);
vector<vector<int>> answer(n);
long long ans = 0;
vector<pll> vec;
for(ll i = 0; i < n; i++){
answer[i].resize(m, -1);
cn[i] = m - 1;
for(ll j = 0; j < k; j++){
ans -= a[i][j];
vec.pb(Mp(a[i][j] + a[i][m - k + j], i));
}
}
sort(all(vec), greater<pll>());
for(ll i = 0; i < n * k / 2; i++){
if(cnt[vec[i].S] == k) continue;
cnt[vec[i].S]++;
ans += vec[i].F;
}
vector<pll> b;
for(ll i = 0; i < n; i++){
c2[cnt[i]].pb(i);
b.pb(Mp(cnt[i], i));
}
for(ll i = 0; i < k; i++){
sort(all(b), greater<pll>());
for(ll j = 0; j < n / 2; j++){
answer[b[j].S][cn[b[j].S]--] = i;
b[j].F--;
}
}
for(ll i = 0; i < n; i++){
for(ll j = 0; j < m; j++){
if(~answer[i][j]) vis[i][answer[i][j]] = 1;
}
cn[i] = 0;
for(ll j = 0; j < k; j++){
if(!vis[i][j]) answer[i][cn[i]++] = j;
}
}
allocate_tickets(answer);
return ans;
}
