#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	long long N;
	int M, K, D, S;
	cin >> N >> M >> K >> D >> S;
	vector<int> A(M), B(M); vector<long long> PreC(M);
	for (int i = 0; i < M; ++i) {
		cin >> A[i] >> B[i] >> PreC[i];
	}
	vector<long long> SC = PreC;
	sort(SC.begin(), SC.end());
	SC.erase(unique(SC.begin(), SC.end()), SC.end());
	vector<int> C(M);
	for (int i = 0; i < M; ++i) {
		C[i] = lower_bound(SC.begin(), SC.end(), PreC[i]) - SC.begin();
	}
	N = min(N, (long long)(SC.size() + 1));
	vector<int> wait(N);
	priority_queue<pair<int, int> > que;
	for (int i = 0; i < N; ++i) {
		que.push(make_pair(0, i));
	}
	int firstS = S, lastS = -1;
	for (int i = 0; i < M; ++i) {
		while (S + D < A[i] && K > 0) {
			while (-que.top().first != wait[que.top().second]) que.pop();
			pair<int, int> u = que.top();
			S = max(S + D, -u.first);
			--K;
			if (K == 0) lastS = S;
		}
		wait[C[i]] = max(wait[C[i]], A[i]) + B[i];
		que.push(make_pair(-wait[C[i]], C[i]));
	}
	while (K > 0) {
		while (-que.top().first != wait[que.top().second]) que.pop();
		pair<int, int> u = que.top();
		S = max(S + D, -u.first);
		--K;
		if (K == 0) lastS = S;
	}
	cout << lastS - firstS << endl;
	return 0;
}
