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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  int D=0;
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
   long long n,m,k;
   long long wynik=0;
  cin>>n>>m>>k;

  long long t[n][m];
  int czymalejacy[n];
  vector<int> malejacy;
  vector<int> rosnacy;
  int ilezjedzone[n];
  long long srednie[n];
  long long sumy[n];
  vector<pair<long long,int>> srednie2;
  
  for (int i=0;i<n;i++){
    
    for (int j=0;j<m;j++){
      cin>>t[i][j];
    }
    if (t[i][0] > t[i][m-1]){
      czymalejacy[i]=1;
      malejacy.push_back(i);
    } else {
      czymalejacy[i]=0;
      rosnacy.push_back(i);
    }
    ilezjedzone[i]=0;
  }


  long long suma=0;
  for (auto i : rosnacy){
      suma=0;
       for (int j=0;j<m;j++){
         suma=suma+t[i][j];
      }
      sumy[i]=suma;
      srednie[i]=suma/m;
      srednie2.push_back({suma,i});
  }
  sort(srednie2.begin(),srednie2.end());
  int maxSrednie = srednie2.size()-1;


    int maxN=0, manM=0;
    long long maxNalesnik=0;
    
  
  
  while(k>0){
    if (D) cout<<k<<endl;
    maxN=0; manM=0;
    maxNalesnik=0;
    
    if (k>m-1){
    for (auto i : malejacy){
      if (ilezjedzone[i]<m && t[i][ilezjedzone[i]] > maxNalesnik){
        maxNalesnik = t[i][ilezjedzone[i]];
        maxN=i;
      }
    }
    } else {
      for (int i=0;i<n;i++){
        if (ilezjedzone[i]<m && t[i][ilezjedzone[i]] > maxNalesnik){
          maxNalesnik = t[i][ilezjedzone[i]];
          maxN=i;
        }
      }
    }
    if (D) cout<<"maxSrednie "<<srednie2[maxSrednie].first<<endl;
    while(maxSrednie>-1 && k>m-1 && maxNalesnik*m<srednie2[maxSrednie].first){
      if (D) cout<<k<<" zjadamCaly "<<srednie2[maxSrednie].second<<" bo srednia "<<srednie2[maxSrednie].first<<endl;;
      ilezjedzone[srednie2[maxSrednie].second]=m;
      k = k-m;
      wynik = wynik + sumy[srednie2[maxSrednie].second];
      maxSrednie=maxSrednie-1;
    }
    k--;
    if (k>-1){
      if (D) cout<<k<<" "<<maxN<<" "<<maxNalesnik<<endl;;
      wynik = wynik + maxNalesnik;
      ilezjedzone[maxN] = ilezjedzone[maxN]+1;
    }
  }

  cout<<wynik;
  return 0;
}