1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
using ll = long long;

int main()
{
    cin.tie(0)->sync_with_stdio();
    int n, m, k;
    cin>>n>>m>>k;
    vector<vector<ll>> vecs;
    vector<ll> vec2(1, 1e18);
    for(int i=0; i<n; i++) {
        vector<ll> v(m);
        for(auto& x : v) {
            cin>>x;
        }
        if(v.front() >= v.back()) {
            vec2.insert(vec2.end(), v.cbegin(), v.cend());
        } else {
            vecs.push_back(v);
        }
    }
    ranges::sort(vec2, greater<ll>{});
    vec2[0] = 0;
    for(auto& x : vecs) {
        ll sm = 0;
        for(auto& y : x) {
            y = sm = sm + y;
        }
    }
    for(int i=1; i<vec2.size(); i++)
        vec2[i] += vec2[i-1];
    if(vecs.empty()) {
        cout<<vec2[k]<<"\n";
        return 0;
    }
    vector<ll> res(m*vecs.size());
    vector<multiset<ll, greater<ll>>> msts(m-1);
    for(int j=0; j<m-1; j++) {
        for(const auto& x : vecs)
            msts[j].insert(x[j]);
    }
    vector<ll> mins(m-1, 1e18);
    ll S = 0;
    ranges::sort(vecs, [](const vector<ll>& lhs, const vector<ll>& rhs) {
        return lhs.back() > rhs.back();
    });
    for(int l=0; l<vecs.size(); l++) {
        for(int j=0; j<m-1; j++) {
            res[l*m + j] = max(S + *msts[j].begin(),
                               S - mins[j] + vecs[l].back());
        }
        for(int j=0; j<m-1; j++) {
            msts[j].erase(msts[j].find(vecs[l][j]));
            mins[j] = min(mins[j], vecs[l].back() - vecs[l][j]);
        }
        S += vecs[l].back();
        res[l*m+m-1] = S;
    }
    ll fin = vec2.size() > k ? vec2[k] : 0;
    for(int i=max<int>(0, k - res.size()); i < min<int>(k, vec2.size()); i++) {
        fin = max(fin, vec2[i] + res[k-1-i]);
    }
    cout<<fin<<"\n";
}