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
#include<bits/stdc++.h>
#define VAR(i,n) __typeof(n) i = (n)
#define loop(i,j,s) for(int i=j;i<s;i++)
#define loopback(i,j,s) for(int i=j;i>=s;i--)
#define foreach(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)
#define pln( x ) cout << x << "\n"
#define ps( x ) cout << x << " "
#define entr cout << "\n"
#define pcnt(i) __builtin_popcount(i)
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define SIZE(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef vector<ll> VL;
typedef vector<vector<int> > VVI;
typedef vector<vector<long long> > VVLL;
const int INFTY=20000000;
const int MAX=500100;
const int MOD=10000000;
//------------------------------------------
// Non-increasing stacks: marginals decrease -> greedy
// Non-decreasing stacks: eat 0 or m, at most 1 partial

int n,m,k;

int main(){
	ios_base::sync_with_stdio(0);
    cin>>n>>m>>k;

    VL conc;
    vector<VL> conv;

    loop(i,0,n){
        VL row(m);
        loop(j,0,m) cin>>row[j];
        bool inc = (m>=2 && row[0] < row[m-1]);
        if(inc){
            VL p(m+1, 0);
            loop(j,0,m) p[j+1] = p[j] + row[j];
            conv.pb(p);
        } else {
            loop(j,0,m) conc.pb(row[j]);
        }
    }

    // concave marginals: sort desc, prefix sums
    sort(ALL(conc), greater<ll>());
    int cs = SIZE(conc);
    VL cp(cs+1, 0);
    loop(i,0,cs) cp[i+1] = cp[i] + conc[i];

    // convex stacks: sort by total desc, prefix sums
    int nc = SIZE(conv);
    sort(ALL(conv), [&](const VL& a, const VL& b){ return a[m] > b[m]; });
    VL vp(nc+1, 0);
    loop(i,0,nc) vp[i+1] = vp[i] + conv[i][m];

    ll ans = 0;

    // case 1: t full convex + concave fill
    loop(t,0,nc+1){
        if((ll)t*m > k) break;
        int b = k - t*m;
        if(b > cs) continue;
        ans = max(ans, vp[t] + cp[b]);
    }

    // case 2: t full + 1 partial convex (partial must NOT be in full set)
    VL smax(nc+1), pswap(nc+1);
    loop(j,1,m){
        // smax[t] = best conv[r][j] for rank r >= t
        smax[nc] = -1;
        loopback(r, nc-1, 0) smax[r] = max(smax[r+1], conv[r][j]);

        // pswap[t] = best (conv[r][j] - conv[r][m]) for rank r < t
        // used when swapping a full stack to partial, bringing in rank t
        pswap[0] = (ll)-1e18;
        loop(r, 0, nc) pswap[r+1] = max(pswap[r], conv[r][j] - conv[r][m]);

        loop(t,0,nc){
            int b = k - t*m - j;
            if(b < 0) break;
            if(b > cs) continue;

            // option A: partial from rank >= t (not in full set)
            if(smax[t] >= 0)
                ans = max(ans, vp[t] + smax[t] + cp[b]);

            // option B: swap one full (rank < t) to partial, add rank t as full
            if(t > 0 && t < nc && pswap[t] > (ll)-1e18)
                ans = max(ans, vp[t+1] + pswap[t] + cp[b]);
        }
    }

    pln(ans);
}