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
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>

using namespace std;

int main() {
    // std::ios_base::sync_with_stdio(false);
    // std::cin.tie(NULL);
    
    long long n,m,k,xx;
    cin>>n>>m>>k;

    vector<long long> desc;
    vector<long long> desc_prefix;

    vector<vector<long long>> asc;
    vector<vector<long long>> asc_prefix;


    long long counter = 0;
    bool desc_ = false;
    for (long long i=0;i<n;i++) {
        vector<long long> pom;
        desc_ = false;

        for (long long j=0;j<m;j++) {
            cin>>xx;
            if (j!=0 and xx < pom.back()) desc_ = true;
            pom.push_back(xx);
        }

        if (desc_) {
            for (long long j=0;j<m;j++) {
                desc.push_back(pom[j]);
            }
        } else {
            counter++;
            asc.push_back(pom);
        }
    }
    sort(desc.begin(),desc.end(), [](long long a,long long b) {return a>b;});

    asc_prefix.resize(asc.size());

    for (long long i=0;i<desc.size();i++) if (i==0) desc_prefix.push_back(desc[0]); else desc_prefix.push_back(desc[i]+desc_prefix[i-1]);
    for (long long i=0;i<asc.size();i++) {
        for (long long j=0;j<asc[0].size();j++) if (j==0) asc_prefix[i].push_back(asc[i][0]); else asc_prefix[i].push_back(asc[i][j]+asc_prefix[i][j-1]);
    }

    vector<pair<long long,long long>> asc_endings;

    for (long long i=0;i<asc.size();i++) asc_endings.emplace_back(asc_prefix[i][m-1],i);

    sort(asc_endings.begin(),asc_endings.end(),[](auto a,auto b){return a>b;});

    long long maks = 0;
    vector<long long> visited(n,-1);

    vector<long long> asc_endings_prefix;

    for (long long i=0;i<asc_endings.size();i++) if (i==0) asc_endings_prefix.push_back(asc_endings[0].first); else asc_endings_prefix.push_back(asc_endings[i].first+asc_endings_prefix[i-1]);

    for (long long i=0;i<=k;i++) { // tutaj se bierzemy i elementow z tych fajnych malejacych ciagow

        if (i > desc.size()) break;

        long long act_maks=(i==0) ? 0 : desc_prefix[i-1];

        long long rest = k-i;


        long long l =0;
        //long long l=rest/m;
        //act_maks += asc_endings_prefix[l];
        // musimy tez pamietac ze visited od 1 do l są ustawione tak jakby na i
        while (rest >= m) {
            if (l >= asc_endings.size()) break;

            act_maks += asc_endings[l].first;
            rest-=m;
            visited[asc_endings[l].second] = i;
            l++;
        }

        if (rest == 0) {
            maks = max(maks,act_maks);
            continue;
        }

        long long additional = 0;
        for (long long j=0;j<asc.size();j++) {
            if (visited[j] != i) {
                additional = max(additional,asc_prefix[j][rest-1]);
            } else {
                if (l < asc_endings.size()) {
                    long long add2 = asc_prefix[j][rest - 1] - asc_prefix[j][m - 1] + asc_endings[l].first;

                    additional = max(additional, add2);
                }
            }
        }
        act_maks += additional;

        maks = max(maks, act_maks);
    }
    // tutaj przypadek jak zostaje

    cout<<maks<<"\n";
    return 0;
}