#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include "tickets.h"
using namespace std;
#define ll long long
vector<vector<ll>> x;
vector<vector<pair<ll, ll>>> dp;
ll n, m;
pair<ll, ll> makeDp(ll indx, ll used_high){
if(used_high > indx+1) return{-1, -1};
if(dp[indx][used_high].first != -1) return dp[indx][used_high];
if(indx == 0){
if(used_high == 1) return dp[indx][used_high] = {x[indx][m-1], m-1};
if(used_high == 0) return dp[indx][used_high] = {-x[indx][0], 0};
}
dp[indx][used_high] = {makeDp(indx-1, used_high).first - (ll)x[indx][0], 0};
if(used_high && dp[indx][used_high].first < makeDp(indx-1, used_high-1).first + (ll)x[indx][m-1]){
dp[indx][used_high] = {makeDp(indx-1, used_high-1).first + (ll)x[indx][m-1], m-1};
}
return dp[indx][used_high];
}
ll find_maximum(int k, vector<vector<int>> x1){
n = x1.size();
m = x1[0].size();
x.assign(n, vector<ll>(m, 0));
vector<vector<int>> arr(n, vector<int>(m, -1));
ll ans = 0;
for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) x[i][j] = (ll)x1[i][j];
if(m == 1){
sort(x.begin(), x.end());
for(ll i = 0; i<n/2; i++) ans -= (ll)x[i][0];
for(ll i = n/2; i<n; i++) ans += (ll)x[i][0];
return ans;
}
else if(k == 1){
dp.assign(n, vector<pair<ll, ll>>(n, pair<ll, ll>(-1, -1)));
ans = makeDp(n-1, n/2).first;
ll uh = n/2;
for(ll i = n-1; i>=0; i--){
arr[i][dp[i][uh].second] = 0;
if(dp[i][uh].second == m-1) uh--;
}
return ans;
}
else if(k == m){
vector<int> allValues;
for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) allValues.push_back(x[i][j]);
sort(allValues.begin(), allValues.end());
map<int, int> smallV;
for(int i = 0; i<(n*m)/2; i++) smallV[allValues[i]] ++;
for(int i = 0; i<n; i++) for(int j = 0; j<m; j++) {
if(smallV[x[i][j]]){
smallV[x[i][j]]--;
ans -= (ll)x[i][j];
x[i][j] = 0;
}
else{
ans += (ll)x[i][j];
x[i][j] = 1;
}
}
priority_queue<pair<int, int>> pq;
vector<int> takenZ(n, 0);
for(int i = 0; i<n; i++){
pair<int, int> p = {0, i};
for(int j = 0; j<m; j++) p.first += x[i][j];
pq.push(p);
}
for(int i = 0; i<k; i++){
vector<pair<int, int>> add;
int j = 0;
while(j<n/2){
add.push_back(pq.top());
add[j].first --;
arr[pq.top().second][m - pq.top().first] = i;
j++;
pq.pop();
}
while(!pq.empty()){
arr[pq.top().second][takenZ[pq.top().second]] = i;
takenZ[pq.top().second] ++;
add.push_back(pq.top());
pq.pop();
}
for(int i = 0; i<add.size(); i++) pq.push(add[i]);
}
// allocate_tickets(arr);
}
else{
priority_queue<pair<int, int>> pq;
vector<int> takenZ(n, 0);
for(int i = 0; i<n; i++){
pair<int, int> p = {0, i};
for(int j = 0; j<m; j++) p.first += x[i][j];
pq.push(p);
}
for(int i = 0; i<k; i++){
vector<pair<int, int>> add;
int j = 0;
while((j<n/2 || pq.top().first == m-i) && pq.top().first != 0){
add.push_back(pq.top());
add[j].first --;
arr[pq.top().second][m - pq.top().first] = i;
j++;
pq.pop();
}
while(!pq.empty()){
arr[pq.top().second][takenZ[pq.top().second]] = i;
takenZ[pq.top().second] ++;
add.push_back(pq.top());
pq.pop();
}
for(int i = 0; i<add.size(); i++) pq.push(add[i]);
ans += (ll)min((ll)j, (ll)n-j);
}
}
allocate_tickets(arr);
return ans;
}
// int main(void){
// freopen("input.txt", "r", stdin);
// int n1, m1, k1;
// cin>>n1>>m1>>k1;
// vector<vector<int>> t;
// t.assign(n1, vector<int>(m1, 0));
// for(int i = 0; i<n1; i++) for(int j = 0; j<m1; j++) cin>>t[i][j];
// cout<<find_maximum(k1, t);
// }
