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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include "bits/stdc++.h"

#define all(v) (v).begin(), (v).end()
#define st first
#define nd second
#define pb push_back
#define printv(a) { for(auto u : a) cout<<u<<" "; cout<<"\n"; }
#define debug(x) cerr << #x << " = " << x << '\n';

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int,int>;

const int MAXN = 300050;
const ll INF = -1000000000000000000ll;

set<pair<ll,ll> > prefiksy[MAXN];

ll rosnace[MAXN], malejace[MAXN];

ll small[MAXN];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<ll> > mal, ros, pref;
    for(int i=0;i<n;i++){
        bool rosnie = false;
        vector<ll> v, s;
        for(int j=0;j<m;j++){
            ll a;
            cin>>a;
            v.pb(a);
            s.pb(a);
            if(j != 0) s[j] += s[j-1];
            if(j != 0 && v[j] > v[j-1]) rosnie = true;
        }
        if(rosnie){
            ros.pb(v);
            pref.pb(s);
        }else{
            mal.pb(v);
        }
    }
    vector<pair<ll,int> > kolejnosc;
    for(int i=0;i<ros.size();i++){
        ll akt = 0;
        int pom = 0;
        for(ll p : ros[i]){
            akt += p;
            pom++;
            prefiksy[pom].insert({akt,i});
        }
        kolejnosc.pb({akt,i});
    }
    sort(kolejnosc.begin(),kolejnosc.end());
    reverse(kolejnosc.begin(),kolejnosc.end());
    kolejnosc.pb({INF,INF});
    rosnace[0] = 0;
    ll akt = 0;
    int ktora = 0;
    small[0] = 0;
    for(int i=1;i<=m;i++){
        priority_queue<ll> akt;
        for(int j = 0;j < ros.size();j++){
            int ind = j*m + i;
            int kol = kolejnosc[j].nd;
            akt.push(-(pref[kol][m-1] - pref[kol][i-1]));
            small[ind] = -akt.top();
        }
    }

    for(int i=1;i <= ros.size() * m;i++){
        if(i%m == 0){
            ktora = i / m - 1;
            auto [val,ind] = kolejnosc[ktora];
            akt += val;
            rosnace[i] = akt;
            ll pom = 0;
            int j = 0;
            for(ll p : ros[ind]){
                j++;
                pom += p;
                prefiksy[j].erase({pom,ind});
            }
        }else{
            ll nastepny = kolejnosc[ktora+1].st;
            rosnace[i] = max(akt + (*prefiksy[i % m].rbegin()).st, akt + nastepny - small[i]);
        }
    }

    for(int i = ros.size() * m + 1;i <= k;i++) rosnace[i] = INF;

    priority_queue<pair<ll,int> > pq;
    for(int i=0;i<mal.size();i++){
        pq.push({mal[i][0], i * m});
    }
    malejace[0] = 0;

    for(int i = 1;i<=mal.size() * m;i++){
        auto [val,ind] = pq.top();  
        pq.pop();
        malejace[i] = malejace[i-1] + val;
        int pozycja_ogolna = ind + 1, pozycja_tablicowa = ind / m, pozycja_szczegolna = ind % m + 1;
        if(pozycja_ogolna % m != 0){
            pq.push({mal[pozycja_tablicowa][pozycja_szczegolna], pozycja_ogolna});
        }
    }

    for(int i = mal.size() * m + 1;i<=k;i++) malejace[i] = INF;

    ll wyn = 0;
    for(int i=0;i<=k;i++){
        wyn = max(wyn, rosnace[i] + malejace[k - i]);
    }
    cout<<wyn<<endl;
    _Exit(0);
}