#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif // LOCAL

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct machine
{
    int in, out;
};

void solve_test (istream &cin, ostream &cout)
{
    int n, m;
    cin >> n >> m;

    int s, k;
    cin >> s >> k;

    vector<vector<machine>> type(n - 1);
    for (int i = 0; i < m; i++)
    {
        int t, in, out;
        cin >> t >> in >> out;
        --t;
        type[t].push_back(machine{in, out});
    }

    int cur = s;
    for (int i = 0; i < n - 1; i++)
    {
        vector<int> dp(cur + 1, 0);

        for (const auto &it : type[i])
        for (int j = 0; j <= cur - it.in; j++)
            dp[j + it.in] = max(dp[j + it.in], dp[j] + it.out);

        cur = *max_element(dp.begin(), dp.end());
        if (cur >= k)
            cur = k;
    }

    cout << cur << endl;
}

void solve (istream &cin, ostream &cout)
{
    int t;
    cin >> t;

    for (int i = 0; i < t; i++)
        solve_test(cin, cout);
}

int main()
{
    #ifdef LOCAL
        ifstream in("input.txt");
        ofstream out("output.txt");
        solve(in, out);
    #else
        solve_test(cin, cout);
    #endif
}