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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}());
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
// head

const int N=5e3+5;

#define INF 0x3f3f3f3f

template<class T> inline void read(T &x) {
    x=0; int c=getchar(),f=1;
    for (;!isdigit(c);c=getchar()) if (c==45) f=-1;
    for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0');
}

int main() {
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    vector<vector<ll>> a(n+1,vector<ll>(m+1,0));
    rep(i,1,n+1) rep(j,1,m+1) scanf("%lld",&a[i][j]);
    vector<ll> inv_st_val;
    vector<vector<ll>> st_prefs;
    vector<ll> st_sum;
    rep(i,1,n+1) {
        if (a[i][m]-a[i][1]>0) {
            vector<ll> pref(m+1,0);
            rep(j,1,m+1) pref[j]=pref[j-1]+a[i][j];
            st_sum.pb(pref[m]);
            st_prefs.pb(move(pref));
        } else rep(j,1,m+1) inv_st_val.pb(a[i][j]);
    }
    int p=SZ(st_sum);
    VI idx(p);
    iota(all(idx),0);
    sort(all(idx),[&](int i,int j) {
        return st_sum[i]>st_sum[j];
    });
    sort(all(st_sum));
    reverse(all(st_sum));
    vector<ll> st_sum_pref(p+1,0);
    rep(i,1,p+1) st_sum_pref[i]=st_sum_pref[i-1]+st_sum[i-1];
    vector<vector<ll>> max_pref(p+1,vector<ll>(m+1,0)),min_suf(p+1,vector<ll>(m+1,LLONG_MAX));
    rep(j,1,m+1) {
        per(i,1,p+1) max_pref[i][j]=max((i<p)?max_pref[i+1][j]:0,st_prefs[idx[i-1]][j]);
        rep(i,1,p+1) min_suf[i][j]=min((i>1)?min_suf[i-1][j]:LLONG_MAX,st_prefs[idx[i-1]][m]-st_prefs[idx[i-1]][j]);
    }
    sort(all(inv_st_val));
    reverse(all(inv_st_val));
    int q=SZ(inv_st_val);
    vector<ll> inv_st_val_pref(q+1,0);
    rep(i,1,q+1) inv_st_val_pref[i]=inv_st_val_pref[i-1]+inv_st_val[i-1];
    auto get_inv_st_val_pref=[&](int x)->ll{
        if (x<=0) return 0;
        return inv_st_val_pref[min(q,x)];
    };
    ll ans=get_inv_st_val_pref(k);
    for (int i=0;i<=p&&i*m<=k;i++) {
        int r=k-i*m;
        ans=max(ans,st_sum_pref[i]+get_inv_st_val_pref(r));
        for (int j=1;j<m&&j<=r;j++) {
            if (i<p) ans=max(ans,st_sum_pref[i]+max_pref[i+1][j]+get_inv_st_val_pref(r-j));
            if (i>0&&i<p) ans=max(ans,st_sum_pref[i+1]-min_suf[i][j]+get_inv_st_val_pref(r-j));
        }
    }
    printf("%lld\n",ans);
}