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
#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<long long> g, t, pg, pt;
vector<vector<long long>> r;

bool wiekszy(long long a,long long b){
    return a>b;
}

void wczytaj(){
    cin >> n >> m >> k;
    
    for(int i=0; i<n; ++i){
        vector<long long> v(m);
        
        for(int j=0; j<m; ++j) cin >> v[j];
        
        if(v[0] >= v[m-1]){
            for(int j=0; j<m; ++j) g.push_back(v[j]);
        }else{
            vector<long long> p(m+1, 0);
            
            for(int j=0; j<m; ++j) p[j+1]=p[j]+v[j];
            
            r.push_back(p);
            t.push_back(p[m]);
        }
    }
}

void sortuj(){
    sort(g.begin(),g.end(), wiekszy);
    sort(t.begin(),t.end(), wiekszy);

    pg.push_back(0);
    for(int i=0; i<(int)g.size(); ++i) pg.push_back(pg[i]+g[i]);
        
    pt.push_back(0);
    for(int i=0; i<(int)t.size(); ++i) pt.push_back(pt[i]+t[i]);
}

long long zlicz(){
    long long w=0;
    int nt=(int)t.size();
    int ng=(int)g.size();

    for(int i=0; i<(int)r.size(); ++i){
        long long ssuma=r[i][m];
        
        for(int d=1; d<m && d<=k; ++d){
            int wolne=k-d;
            int f=wolne/m;
            long long zf=0;
            int uf=0;
            
            if (f>0){
                if(f<=nt && ssuma>=t[f-1]){
                    int zas=f+1;
                    if(zas>nt) zas=nt;
                    zf=pt[zas]-ssuma;
                    uf=zas-1;
                }else{
                    uf=f;
                    if(uf>nt) uf=nt;
                    zf=pt[uf];
                }
            }
            int resz=k-d-uf*m;
            if(resz<0) resz=0;
            if(resz>ng) resz=ng;
            long long akt=r[i][d]+zf+pg[resz];
            if(akt>w) w=akt;
        }
    }

    for(int i=0; i<=nt; ++i){
        long long zm=(long long)i*m;
        if(zm<=k){
            int zost=(int)(k-zm);
            if(zost>ng) zost=ng;
            long long akt=pt[i]+pg[zost];
            if(akt>w) w=akt;
        }
    }
    return w;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    wczytaj();
    sortuj();
    cout<<zlicz()<<endl;
    
    return 0;
}