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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll I=2e18;
vector<ll> solveI(vector<vector<ll> > a){
  if(a.empty())return {0};
  int n=a.size(),m=a[0].size();
  for(auto &v:a)partial_sum(v.begin(),v.end(),v.begin());
  vector<int> p(n);
  iota(p.begin(),p.end(),0);
  sort(p.begin(),p.end(),[&](int x,int y){
    return a[x].back()>a[y].back();
  });
  vector<ll> ps(n);
  for(int i=0;i<n;i++)
    ps[i]=(i?ps[i-1]:0)+a[p[i]].back();
  vector<ll> w(n*m+1);
  for(int r=0;r<m;r++){
    vector<ll> sf(n),pr(n);
    for(int i=n-1;~i;i--)
      sf[i]=max(i<n-1?sf[i+1]:0,r?a[p[i]][r-1]:0);
    for(int i=0;i<n;i++)
      pr[i]=max(i?pr[i-1]:-I,(r?a[p[i]][r-1]:0)-a[p[i]].back());
    for(int i=0;i<n;i++)
      w[i*m+r]=max((i?ps[i-1]:0)+sf[i],ps[i]+pr[i]);
  }
  for(auto &v:a)w[n*m]+=v.back();
  return w;
}
vector<ll> solveD(vector<vector<ll> > a){
  if(a.empty())return {0};
  vector<ll> r;
  for(auto &v:a)for(auto &i:v)r.emplace_back(i);
  sort(r.begin(),r.end(),greater<>());
  partial_sum(r.begin(),r.end(),r.begin());
  return r.insert(r.begin(),0),r;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m,k; cin>>n>>m>>k;
  vector a(n,vector<ll>(m));
  for(auto &v:a)for(auto &i:v)cin>>i;
  vector<vector<ll> > vI,vD;
  for(auto &v:a){
    if(is_sorted(v.begin(),v.end()))vI.emplace_back(v);
    else vD.emplace_back(v);
  }
  auto rI=solveI(vI),rD=solveD(vD);
  ll c=0;
  for(int i=0;i<=min((int)rI.size()-1,k);i++)
    if(k-i<rD.size())c=max(c,rI[i]+rD[k-i]);
  cout<<c<<endl;
  return 0;
}