C: 買い出し - Shopping -

物語

磯野の姉であるサゾエさんは，『あれ』や『あれ』で遊んでいる磯野と中島のために夕食を作ってあげることにしました．あいにく，冷蔵庫には食材が残り僅かしか無く，サゾエさんは買い出しに行くことにしました．幾つか食材を買おうとしているサゾエさんですが，大変陽気であるため一度に一品のみレジで会計してしまいます．このままでは遊んでいた磯野と中島が買い物を終える前に帰ってきてしまい，夕食を準備することが出来ないかもしれません．そこで，サゾエさんの友人であるあなたは，サゾエさんのためにサゾエさんの買い物にかかる最小の時間を求めてください．

問題

とあるスーパーにN個のレジがあり，それぞれ1〜Nまでの番号がついている．

また，客がM人居て，それぞれ1〜Mまでの番号がついている．i番目の客は，時刻a_iにc_i番目のレジに並び，会計にb_iの時間がかかる．1人の客は一度だけ会計をする．

ここで，ある客が並んだレジに既に人が並んでいる場合，その客は既に並んでいる人全員の会計が終了した後に会計をする．i番目の客と，i+1番目の客が同じレジに並んでいたとすると，i番目の客の会計開始時刻がtであった場合，i番目の客の会計終了時刻はt+b_i，i+1番目の客の会計開始時刻はt+b_i，そして，i+1番目の客の会計終了時刻は，t+b_i+b_{i+1}となる．

サゾエさんは1人の客である．しかし，サゾエさんは例外的にK回会計をする．また，会計にかかる時間は0，すなわちサゾエさんの会計開始時刻をtとすると，会計終了時刻はtとなり，次の客の会計開始時刻はtとなる．その後，サゾエさんが再度レジに並ぶ際，会計終了時刻tから品定めにかかる時間Dだけ経ってから並ばなければいけない．つまり，再度レジに並ぶことができる時刻はt+Dとなる．

また，サゾエさんは時刻Sにスーパーにやって来る．そして，時刻SからDだけ経った時刻S+Dに，初めてサゾエさんはレジに並ぶことが出来る．

N，M，K，D，Sと，1番目〜M番目までの客の情報がそれぞれ与えられるので，サゾエさんがスーパーに来てから最後の会計を終えるまでにかかる時間の最小値を求めよ．この時，異なる2人の客が同じ時刻に同じレジに並ぶことは無いとし，サゾエさんとほかの人が同時にレジに並ぼうとした場合，サゾエさんは常にほかの客に順番を譲ることとする．

入力形式

入力は次の形式で与えられる．

N M K D S
a_1 b_1 c_1
...
a_M b_M c_M

1行目にスーパーにあるレジの数N（1 ≤ N ≤ 10^{15}），訪れる客の数M(1 ≤ M ≤ 10^5)，サゾエさんがレジを回る回数K(1 ≤ K ≤ 10^4)，サゾエさんの品定めにかかる時間D(1 ≤ D ≤ 10^4)，サゾエさんがスーパーに来る時刻S(1 ≤ S ≤ 10^4)が空白区切りで与えられる．

続くM行に訪れる客の情報が与えられる．M行のうち，i(1 ≤ i ≤ M)行目には，i番目の客がレジに来る時刻a_i(1 ≤ a_i ≤ 10^4)，会計にかかる時間b_i(1 ≤ b_i ≤ 10^4)，やって来るレジの番号c_i(1 ≤ c_i ≤ N)が空白区切りで与えられる．ここで2 ≤ Mの時，全てのi(1 ≤ i ≤ M−1)について，a_i ≤ a_{i+1}が成立する．

なお，入力が非常に大きくなる場合があるため，入力の受け取りには高速な関数を用いることを推奨する．

出力形式

サゾエさんがスーパーに来てから最後の会計を終えるまでにかかる時間の最小値を1行で出力せよ．

入力例1

3 9 3 2 3
1 2 3
1 1 2
2 3 1
3 4 2
4 1 3
4 1 1
5 1 1
6 2 3
7 2 2

出力例1

6

時間5にレジ3，時間7にレジ1，時間9にレジ2に並ぶ． サゾエさんの入店時間が時間3なので初めてレジに並んでから時間6で3回の会計が終了する． また，時間9に並ぶレジはレジ1，もしくはレジ3でも最適解になる

入力例2

3 9 3 1 3
1 2 3
1 1 2
2 3 1
3 4 2
4 1 3
4 1 1
5 1 1
6 2 3
7 2 2

出力例2

5

入力例3

1 3 3 2 1
1 1 1
2 2 1
3 2 1

出力例3

9