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


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N,M,K;
    cin>>N>>M>>K;
    long long tab[N][M];
    long long pole_rosnacych=0;
    long long pole_malejacych=0;
    priority_queue<pair<long long,pair<int,int>>> malejace; 
    priority_queue<pair<long long,pair<int,int>>> rosnace;
    long long suma=0;
    
    for (int i=0;i<N;i++){
        long long akt=0;
        for (int j=0;j<M;j++){
            cin>>tab[i][j];
            akt+=tab[i][j];
        }
        if (tab[i][0]<tab[i][M-1]){
            suma+=akt;
            pole_rosnacych+=M;
            rosnace.push({-tab[i][M-1],{i,M-1}});
        } else{
            pole_malejacych+=M;
            malejace.push({tab[i][0],{i,0}});
        }
    }
    
    int ile_rosnacych=pole_rosnacych;
    int ile_malejacych=0;
    long long ans=0;

    for (int i=0;i<=K;i++){
        int mal=i;
        int ros=K-i;
        if (mal>pole_malejacych or ros>pole_rosnacych) continue;
        while (ile_malejacych<mal){
            pair<long long,pair<int,int>> akt;
            akt=malejace.top();
            suma+=akt.first;
            malejace.pop();
          //  cout<<akt.first<<" "<<akt.second.first<<" "<<akt.second.second<<" dodajemy\n";
            if (akt.second.second+1<M){
                malejace.push({tab[akt.second.first][akt.second.second+1],{akt.second.first,akt.second.second+1}});    
            }
            ile_malejacych++;
        }
        while (ile_rosnacych>ros){
            pair<long long,pair<int,int>> akt;
            akt=rosnace.top();
            suma-=(-akt.first);
          //  cout<<akt.first<<" "<<akt.second.first<<" "<<akt.second.second<<" usuwamy\n";
                rosnace.pop();
            if (akt.second.second-1>=0){
                rosnace.push({-tab[akt.second.first][akt.second.second-1],{akt.second.first,akt.second.second-1}});  
            }
            ile_rosnacych--;
        }
     //   cout<<mal<<" "<<ros<<" "<<suma<<"\n";
        ans=max(ans,suma);
    }
    cout<<ans<<"\n";
}