Student T is very enthusiastic about running. To make running more interesting, he decided to create an app called "Daily Running Check-in," which allows users to check in by running every day.

After development, Student T planned a trial run and asked Student Y for help. The trial run lasts for $n$ days, numbered from $1$ to $n$.

For Student Y, if he chooses to check in by running on a certain day, his energy value decreases by $d$. Initially, his energy value is $0$, and his energy value can be negative during the trial run.

Furthermore, Student Y will not check in by running for more than $k$ consecutive days; that is, there cannot exist $1 \le x \le n - k$ such that he checked in by running on every day from day $x$ to day $x + k$.

Student T designed $m$ challenges in the app. The $i$-th ($1 \le i \le m$) challenge is described by three positive integers $(x_i, y_i, v_i)$, which means that if the user has already checked in by running for at least $y_i$ consecutive days by day $x_i$ (i.e., he completed running check-ins from day $x_i - y_i + 1$ to day $x_i$), 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 what is the maximum energy value he can achieve after the $n$ days of the trial run are over.

Input

The input is read from the file run.in.

The test cases for this problem contain multiple test sets. The first line of the input contains two integers $c$ and $t$, representing the test point number and the number of test sets, respectively. For the sample, $c$ indicates that this sample has the same constraints as test point $c$.

Next, for each test set: The first line contains four positive integers $n, m, k, d$, representing the number of days of the trial run, the number of challenges, the limit on consecutive days of running check-ins, and the energy value lost per running check-in, respectively. The next $m$ lines each contain three positive integers $x_i, y_i, v_i$, representing a challenge.

Output

Output to the file run.out.

Output a single integer representing the corresponding answer.

Examples

Input 1

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

Output 1

2

Note 1

By checking in on days 1 and 2, and not checking in on day 3, the final energy value obtained is $(-1) + (-1) + 4 = 2$.

Constraints

Let $l_i = x_i - y_i + 1$ and $r_i = x_i$. For all test data, 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$.