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
124
125
126
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric> 

using namespace std;

#define MAX 300100

#define D(x) 
#define D2(x)  x

typedef long long I;

int n,m,k;

vector<I> ros;
vector<vector<I>> mal;

I R[MAX],M[MAX],M2[MAX];

I buf[3*MAX];
I S[MAX];

std::vector<int> indeksy;


void printbuf(int N) {
    printf("buf:\n");

        for(int i=0;i<=m;i++) {
    for(int n=0;n<N;n++) {
            printf("%lld ",buf[i*N+n]);
        }
        printf("\n");
    }

}

int main() {
    scanf("%d %d %d", &n ,&m, &k);
    for(int i=0;i<n;i++) {
        I a;
        deque<I> v;
        for(int j=0;j<m;j++) {
            scanf("%lld", &a);
            v.push_back(a);
        }       
        if(is_sorted(v.rbegin(), v.rend())) ros.insert(ros.end(), v.begin(), v.end());
        else { 
            S[mal.size()] = std::accumulate(v.begin(), v.end(), 0LL);
            v.push_front(0);
            mal.emplace_back(v.begin(), v.end());
        }
    }

    indeksy = std::vector<int>(mal.size());
    std::iota(indeksy.begin(), indeksy.end(), 0);
    std::sort(indeksy.begin(), indeksy.end(), [&](int a, int b) {
        return S[a] > S[b];
    });
  
    I N = mal.size();
    for(int n=0;n<N;n++) {
        for (int i = 2;i<=m;i++) {
            mal[n][i] += mal[n][i-1];
        }
    }

    D(printf("stosy:\n");
    for(int n=0;n<N;n++) {
        for(int i=1;i<=m;i++) {
            printf("%lld ",mal[n][i]);
        }
        printf("\n");
    }
    )

    for(int nn=0;nn<N;nn++) {
        int n = indeksy[nn];
        for(int j=nn;j>0;j--) {
            bool update = false;
            for (int i = 1;i<=m;i++) {
                    I v = max(buf[i*N+j-1] + S[n], buf[m*N+j-1] + mal[n][i]);
                    if (buf[i*N+j] < v) {
                        buf[i*N+j] = v;
                        update = true;
                    }
            }
            if (!update) break;
        }
        int j = 0;
        for (int i = 1;i<=m;i++) {
            if (buf[i*N+j] < mal[n][i]) buf[i*N+j] = mal[n][i];
        }
        D(printbuf(N));
    }


D(    printbuf(N));
D(    for(int i=0;i<N;i++) {
        printf("%lld : %lld, ", S[i], mal[i][m]);
    })

    sort(ros.begin(), ros.end(), std::greater<I>());
    for(int i=0;i<ros.size(); i++) R[i+1]=ros[i];
    for(int i=2;i<=n*m; i++) R[i]+=R[i-1];
 
    for(int i=1;i<=m;i++) {
    for(int n=0;n<N;n++) {
            M2[i+n*m] = buf[i*N+n];
        }
    }
 
    I r = 0;
D(    for(int i=1;i<=n*m;i++) {
        printf("%lld ", M2[i]);
    }
)

    for(int i=0;i<=k;i++) r = max(r, R[i]+M2[k-i]);
    printf("%lld\n", r);

}