P9871 [NOIP2023] Daily Check-in

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?

**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 one line with one integer, the answer for the corresponding testdata group.

**[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$. |Test Point ID|$n \le$|$m \le$|Special Property| |:-:|:-:|:-:|:-:| |$1, 2$|$18$|$10 ^ 2$|None| |$3, 4$|$10 ^ 2$|$10 ^ 2$|None| |$5 \sim 7$|$10 ^ 3$|$10 ^ 3$|None| |$8, 9$|$10 ^ 3$|$10 ^ 5$|None| |$10, 11$|$10 ^ 5$|$10 ^ 3$|None| |$12 \sim 14$|$10 ^ 5$|$10 ^ 5$|None| |$15, 16$|$10 ^ 9$|$10 ^ 5$|A| |$17, 18$|$10 ^ 9$|$10 ^ 5$|B| |$19 \sim 21$|$10 ^ 9$|$10 ^ 5$|C| |$22 \sim 25$|$10 ^ 9$|$10 ^ 5$|None| Special property A: $k\le 10^2$. Special property B: $\forall 1\le i