#!/usr/bin/env python3
n, m = map(int, input().split())
s, k = map(int, input().split())


machines = [[] for _ in range(n-1)]
for _ in range(m):
    target, inp, out = map(int, input().split())
    machines[target-1].append((inp, out))

machines = [sorted(stage, key=lambda x: x[1]/x[0]) for stage in machines]

for stage in range(n-1):
    dp = [-1] * (s+1)
    dp[s] = 0

    for m in machines[stage]:
        for i in range(s, m[0]-1, -1):
            if dp[i] < 0:
                continue
            if i >= m[0]:
                remaining = i - m[0]
                output = dp[i] + m[1]
                if remaining + output <= k:
                    dp[remaining] = max(dp[remaining], output)
                elif remaining + output - dp[i] <= k:
                    dp[remaining] = max(dp[remaining], k-remaining)
            if i>0:
                dp[i-1] = max(dp[i-1], dp[i])

    s = max(dp)

print(s)