#include <iostream>
#include <vector>
#include <algorithm>

// This solution solves the ore processing problem by modeling it as a multi-stage
// dynamic programming problem. The core idea is to calculate the maximum amount of
// material we can produce at each stage, carrying that result forward to the next.

// For each stage of processing (from material `i` to `i+1`), we face a subproblem:
// given a certain amount of input material `i`, what's the maximum amount of
// material `i+1` we can produce? This subproblem is a classic Unbounded Knapsack
// problem. The "items" are the machines, their "weight" is the input material
// consumed, and their "value" is the output material produced. The "knapsack capacity"
// is the amount of input material `i` we have available.

// After solving the knapsack problem for a stage, we get the optimal production
// for every possible amount of consumed input. However, we must also respect the
// global warehouse capacity `k`. The total amount of material in the warehouse
// during a stage (the remaining input material `i` plus the produced material `i+1`)
// cannot exceed `k`. We iterate through all possible consumption amounts to find
// the plan that maximizes the output of material `i+1` without violating this
// capacity constraint.

// The maximum output from one stage becomes the input for the next, and this process
// is repeated for all `n-1` stages.

int main() {
    // Fast I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    long long s, k;
    std::cin >> s >> k;

    // Store machines grouped by their input material type (stage).
    // machines_by_stage[i] holds all machines that convert material i to i+1.
    std::vector<std::vector<std::pair<int, int>>> machines_by_stage(n);
    for (int i = 0; i < m; ++i) {
        int stage, mi, mo;
        std::cin >> stage >> mi >> mo;
        if (stage < n) { // Machines for stages beyond n-1 are irrelevant
            machines_by_stage[stage].push_back({mi, mo});
        }
    }

    long long current_amount = s;

    // Process each stage sequentially from 1 to n-1.
    for (int i = 1; i < n; ++i) {
        // If we have no material to process, we can't make any more.
        if (current_amount == 0) {
            break;
        }

        // DP table for the Unbounded Knapsack problem.
        // produce[j] will store the maximum amount of material i+1 that can be
        // produced by consuming exactly j units of material i.
        std::vector<long long> produce(current_amount + 1, 0);
        
        // Solve the knapsack problem for the current stage.
        for (const auto& machine : machines_by_stage[i]) {
            int cost = machine.first;
            int value = machine.second;
            for (long long j = cost; j <= current_amount; ++j) {
                produce[j] = std::max(produce[j], produce[j - cost] + value);
            }
        }

        // Determine the maximum amount of the next material we can produce,
        // while respecting the warehouse capacity `k`.
        long long max_next_amount = 0;
        for (long long j = 0; j <= current_amount; ++j) {
            long long consumed = j;
            long long produced = produce[j];
            long long remaining = current_amount - consumed;

            // The total material in the warehouse (remaining input + new output)
            // must not exceed the capacity k.
            if (remaining + produced <= k) {
                max_next_amount = std::max(max_next_amount, produced);
            }
        }
        
        // The result of this stage is the input for the next.
        current_amount = max_next_amount;
    }

    std::cout << current_amount << std::endl;

    return 0;
}