Problem Description

Student T is very enthusiastic about running. To make running more fun, he decides to create an app called Daily Check-in, so that users can check in for running every day.

After finishing development, student T plans to do a trial run, and he asks student Y to help. The trial run lasts for $n$ days, numbered from $1$ to $n$.

For student Y, if he chooses to check in for running on some day, his energy value will decrease by $d$. Initially, his energy value is $0$, and during the trial run his energy value may be negative.

Also, student Y will not check in for running continuously for more than $k$ days; that is, there cannot exist $1\le x\le n-k$ such that he checked in for running from day $x$ to day $x+k$.

Student T designed $m$ challenges in the app. The $i$-th challenge ($1\le i \le m$) can be described by three positive integers $(x_i,y_i,v_i)$, meaning that if on day $x_i$ the user has already checked in for running continuously for at least $y_i$ days (i.e. from day $x_i-y_i+1$ to day $x_i$ all days are checked in), then student T will treat the user to a meal, thereby increasing the user’s energy value by $v_i$.

Now student Y wants to know: after the $n$ days of the trial run end, what is the maximum energy value he can reach?

Input Format

This problem’s test points contain multiple groups of testdata.

The first line contains two integers $c$ and $t$, representing the test point ID and the number of testdata groups. For the samples, $c$ indicates that the sample has the same constraints as test point $c$.

Next, for each group of testdata:

• The first line contains four positive integers $n,m,k,d$, representing the number of trial days, the number of challenges, the limit on the maximum consecutive days that student Y can check in for a single running streak, and the energy decrease for each running check-in.
• The next $m$ lines each contain three positive integers $x_i,y_i,v_i$, describing one challenge.

Output Format

Output one line with one integer, the answer for the corresponding testdata group.

1 1
3 2 2 1
2 2 4
3 2 3

2

Hint

[Sample Explanation #1]

Check in for running on days $1,2$, do not check in on day $3$, and in the end you will obtain an energy value of $(-1)+(-1)+4=2$.

[Sample Explanation #2]

This sample satisfies the constraints of test point $3$.

[Sample Explanation #3]

This sample satisfies the constraints of test point $5$.

[Sample Explanation #4]

This sample satisfies the constraints of test point $15$.

[Sample Explanation #5]

This sample satisfies the constraints of test point $17$.

[Sample Explanation #6]

This sample satisfies the constraints of test point $19$.

[Constraints]

Let $l_i=x_i-y_i+1$, $r_i=x_i$​.

For all testdata, it is guaranteed that $1\le t\le 10$, $1\le k\le n\le 10^9$, $1\le m\le 10^5$, $1\le l_i\le r_i\le n$, $1\le d,v_i\le 10^9$.

Special property A: $k\le 10^2$.

Special property B: $\forall 1\le i<m$，$r_i<l_{i+1}$.

Special property C: $\forall 1\le i<j\le m$，$l_i<l_j$，$r_i<r_j$.

Translated by ChatGPT 5