#include <algorithm>
#include <cstdint>
#include <ios>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

template <typename F>
class y_combinator {

private:

    F f;

public:

    explicit y_combinator(F&& f) : f(f) {}

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {

        return f(*this, std::forward<Args>(args)...);

    }

};

template <typename F>
y_combinator(F) -> y_combinator<F>;

void solve() {

    using dp_t = std::vector<std::int64_t>;

    std::int64_t e;
    std::int32_t k;
    std::int32_t n;

    std::cin >> n >> k >> e;

    std::vector<std::int32_t> a(n);
    std::vector<std::int32_t> b(n);
    std::vector<std::int32_t> v(n);

    for (std::int32_t i = 0; i < n; ++i) {
        std::cin >> v[i] >> a[i] >> b[i];
    }

    std::vector<std::int32_t> rs(n);

    y_combinator(
        [&](
            auto self, std::int32_t idx_l, std::int32_t idx_r, std::int32_t lo, std::int32_t hi,
            dp_t dp
        ) -> void {
            if (hi - lo <= 1) {
                for (std::int32_t i = idx_l; i < idx_r; ++i) {
                    rs[i] = hi;
                }
                return;
            }
            const auto apply = [&](
                dp_t dp, std::int32_t idx_l, std::int32_t idx_r, bool tp
            ) -> dp_t {
                for (std::int32_t i = idx_l; i < idx_r; ++i) {
                    const std::int32_t cst = (!tp ? a : b)[i];
                    for (std::int32_t j = k; j >= cst; --j) {
                        dp[j] = std::max(dp[j], dp[j - cst] + v[i]);
                    }
                }
                return dp;
            };
            std::int32_t c_hi = hi;
            const std::int32_t idx_m = (idx_l + idx_r) / 2;
            std::int32_t c_lo = std::max(lo, idx_m - 1);
            dp_t c_dp = apply(dp, lo + 1, c_lo + 1, false);
            while (c_hi - c_lo > 1) {
                const std::int32_t mi = (c_lo + c_hi) / 2;
                const dp_t n_dp = apply(apply(c_dp, c_lo + 1, mi + 1, true), mi + 1, hi, false);
                if (std::accumulate(std::begin(n_dp), std::end(n_dp), std::int64_t()) <= e * k) {
                    c_dp = apply(c_dp, mi, c_hi, false);
                    c_hi = mi;
                } else {
                    c_dp = apply(c_dp, c_lo + 1, mi + 1, true);
                    c_lo = mi;
                }
            }
            rs[idx_m] = c_hi;
            if (idx_l < idx_m) {
                self(idx_l, idx_m, lo, rs[idx_m], apply(dp, rs[idx_m], hi, false));
            }
            if (idx_r > idx_m + 1) {
                self(idx_m + 1, idx_r, rs[idx_m], hi, apply(dp, lo + 1, rs[idx_m], true));
            }
        }
    )(0, n, -1, n, dp_t(k + 1));

    std::cout << std::int64_t(n) * n - std::accumulate(
        std::begin(rs), std::end(rs), std::int64_t()
    ) << '\n';

}

int main() {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}