#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int> > mas, ans;
const int dydis = 1501;
const long long inf = 1e18;
long long dp[dydis][dydis];
pair<int, int> came[dydis][dydis];
vector<int> k1(long long &S) {
vector<pair<int, int> > mn(n, make_pair((int)1e9, -1)), mx(n, make_pair((int)0, -1));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(ans[i][j] != -1) continue;
mn[i] = min(mn[i], make_pair(mas[i][j], j));
mx[i] = max(mx[i], make_pair(mas[i][j], j));
}
}
/// dp[i][j] - jei turiu tik pirmas i eiluciu ir esu paemes lygiai j mn'u, kokia max suma?
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
dp[i][j] = -inf;
came[i][j] = {-1, 0};
}
}
/// dp[-1][0] = 0
for(int i = 0; i < n; i++) {
for(int j = 0; j <= i+1; j++) {
dp[i][j] = -inf;
/// Imu mn:
if(j > 0) {
long long dpvl = (i == 0 ? -mn[i].first : dp[i-1][j-1] - mn[i].first);
if(dpvl > dp[i][j]) {
dp[i][j] = dpvl;
came[i][j] = {i-1, j-1};
}
}
/// Imu mx:
if(j != i+1) {
long long dpvl = (i == 0 ? mx[i].first : dp[i-1][j] + mx[i].first);
if(dpvl > dp[i][j]) {
dp[i][j] = dpvl;
came[i][j] = {i-1, j};
}
}
}
}
vector<int> ret;
int i = n-1;
int j = n / 2;
while(i != -1 || j != 0) {
int ni = came[i][j].first;
int nj = came[i][j].second;
if(nj != j) { // sitas mn
ret.push_back(mn[i].second);
}else {
ret.push_back(mx[i].second);
}
i = ni;
j = nj;
}
reverse(ret.begin(), ret.end());
S = dp[n-1][n / 2];
return ret;
}
long long find_maximum(int k, vector<vector<int>> x) {
mas = x;
ans = x;
for(auto &x : ans) for(auto &y : x) y = -1;
n = x.size();
m = x[0].size();
long long ANS = 0;
for(int i = 0; i < k; i++){
long long answ = 0;
vector<int> kurie = k1(answ);
for(int j = 0; j < n; j++) {
ans[i][kurie[i]] = i;
}
// cout << "ans: "; for(auto &x : kurie) cout << x << " ";
// cout << endl;
ANS += answ;
}
allocate_tickets(ans);
return ANS;
}
//allocate_tickets(answer);
/*
4 2 1
5 9
1 4
3 6
2 7
*/
