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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using ll = long long;
using sz = size_t;
using namespace std;

// make the code less c++-readable:
template<class T> using v = vector<T>; 
template<class T> using vv = v<v<T>>; 
using vi = v<int>; using vll = v<ll>; using vvi = vv<int>; using vvll = vv<ll>;

// hai loading utilities
#define $T template<class T>
#define $Ts template<class... T>
$T T Load() { T v; cin >> v; return v; }
$T auto Loads(int n) { v<T> v; v.reserve(n); while(n--) v.emplace_back(Load<T>()); return v; }
$T auto Loads() { return Loads<T>(Load<int>()); }
template<class T, int N> auto Loada() { array<T, N> a; for (T& v: a) v = Load<T>(); return a; }
$Ts auto Cols(int rows) { tuple<v<T>...> t; while(rows--) [&]<sz... I>(index_sequence<I...>){(std::get<I>(t).push_back(Load<T>()), ...);}(index_sequence_for<T...>{}); return t; }
//$Ts auto Rows(int rows) { v<tuple<T...>> v; while(rows--) { v.emplace_back(Load<T>()...); } return v; } bugged :(
struct _aIV { $T operator vector<T>() { return Loads<T>(n); } sz n; };
struct _aI { $T operator T() { return Load<T>(); } _aIV operator()(sz n) { return {n}; } }; static inline _aI $;  /* int N = $;  vi Y = $(N); */
#define MAKE_LOADER(T, alias) \
  T alias() { return Load<T>(); }   /* int x = Int(); */\
  auto alias##s() { return Loads<T>(); }   /* vector<> xs = Ints(); */\
  auto alias##s(int n) { return Loads<T>(n); }   /* vector<> xs = Ints(7); */\
  template<int N> auto alias##a() { return Loada<T, N>(); }   /* array<> xs = Inta<7>();  */\
// line intentionally left blank
MAKE_LOADER(int, Int)
MAKE_LOADER(long long, LL)
MAKE_LOADER(char, Char)
MAKE_LOADER(string, String)
// kthxbye

constexpr int MAX_H=1'000'000+44;

struct Niesmaczny {
    vll stos;
    ll suma;
};

void test() {
    int N = $;
    int M = $;
    int K = $;

    v<Niesmaczny> niesmaczne;
    ll niewszystkie = 0;
    vll smaczne;

    for (int i = 0; i < N; ++i) {
        vll stos = LLs(M);
        bool smaczny = true;
        ll suma = stos[0];
        for (int j = 0; j < M-1; ++j) {
            suma += stos[j+1];
            if (stos[j] < stos[j+1])
                smaczny = false;
        }
        if (smaczny) {
            for (int j = 0; j < M; ++j)
                smaczne.push_back(stos[j]);
        } else {
            niesmaczne.push_back(Niesmaczny{.stos = std::move(stos), .suma=suma});
            niewszystkie += suma;
        }
    }

    // cerr << "wczyt" << endl;

    sort(smaczne.rbegin(), smaczne.rend());
    sort(niesmaczne.begin(), niesmaczne.end(), [](auto ns1, auto ns2) {
        return ns1.suma > ns2.suma;
    });

    vll najniesmaczniej(niesmaczne.size() * M + 1);
    vll top_resztka(M); // (ile dobranych -1) -> wielkość sumaryczna
    for (int całych = niesmaczne.size(); całych > 0; --całych) {
        najniesmaczniej[całych * M] = niewszystkie;
        // cerr << "NNS[" << ((całych)*M) << "] = " << najniesmaczniej[(całych)*M] << endl;

        niewszystkie -= niesmaczne[całych - 1].suma;

        ll s = 0;
        for (int j = 0; j < M; ++j) {
            s += niesmaczne[całych-1].stos[j];
            top_resztka[j] = max(top_resztka[j], s);
            najniesmaczniej[(całych-1)*M + j+1] = niewszystkie + top_resztka[j];

            // cerr << "NNs[" << ((całych-1)*M + j+1) << "] = " << najniesmaczniej[(całych-1)*M + j+1] << ", bo" <<
            //  "tr[" << j << "]=" << top_resztka[j] << ", a suma="<<niesmaczne[całych-1].suma << ", s = " << s << endl;
        }
    }
    // cerr << "pre" << endl;


    ll ans = 0;
    ll s = 0;
    for (int smacznych = 0; smacznych <= K && smacznych <= smaczne.size(); ++smacznych) {
        if (smacznych)
            s += smaczne[smacznych-1];

        if (K-smacznych >= najniesmaczniej.size()) continue;

        // cerr << "smacznych " << smacznych << ": " << s << " + " << najniesmaczniej[K-smacznych] << endl;

        ans = max(ans, s + najniesmaczniej[K-smacznych]);
    }
    cout << ans << endl;
}


[[maybe_unused]] void jeden_test() { test(); }
[[maybe_unused]] void wiele_test() { int T = $; while (T--) test(); }

int main() {
    jeden_test();
    return 0;
}