#include <bits/stdc++.h> using namespace std; #define int long long void allocate_tickets(vector<vector<signed>> s); int find_maximum(signed k, vector<vector<signed>> x) { int n = x.size(); int m = x[0].size(); vector<vector<signed>> s(n, vector<signed>(m,-1)); vector<int> left(n,0); vector<int> right(n,m-1); int ans = 0; for (int r=0; r<k; r++) { vector<pair<int,int>> p; for (int i = 0; i < n; i++) { p.push_back({x[i][left[i]] + x[i][right[i]], i}); } sort(p.begin(), p.end()); for (int i=0; i<n/2; i++) { int ind = p[i].second; ans -= x[ind][left[ind]]; s[ind][left[ind]] = r; left[ind] ++; } for (int i=n/2; i<n; i++) { int ind = p[i].second; ans -= x[ind][left[ind]]; ans += p[i].first; s[ind][right[ind]] = r; right[ind] --; } } allocate_tickets(s); return ans; }