Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3653
Sleeper's Schedule

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Sleeper has a trouble planning his schedule recently, partly because he wants to watch the UEFA European Championships, partly due to the Topcoder's and the Codeforces' contests. So he wrote a list of the following events' starting time, ending time and values. Apparently, some of the events have conflicting time schedules, so he has to decide whether he should attend an event or not.

What's more, Sleeper has an extremely accurate biological clock, after he stays awake for t time units, he will suffer more and more every time unit from this point to a limit of l time units' length, when he will fall asleep immediately. However he cannot fall asleep before t time units. Sleeper will wake up exactly after k + dt time units. (Here, dt is the extra time units he stays awake last night after the usual t time units.)

Sleeper wants to sleep well and enjoy his life the most, so he comes to you for help. Write a program to calculate the maximum satisfaction value he can get from the following events. Sleeper stays awake for at least t time units and at most t + l time units once, then he has to go to sleep. If he stays awake for t + dt time units he suffer a total extra-staying-awake-time penalty of dt2(dt>0) to his sum of the event values. When Sleeper is awake and have nothing to do, unless he has been awake for more than or exactly t time units, he cannot go to sleep. The final value is the sum value of the events' values minus the extra-staying-awake-time penalty described above.

1. All time point or time scale are integers, and all time are scaled by the same time unit.
2. Time starts from zero, Sleeper has just woke up at this time.


The first line of the input is an integer c, which is the number of test cases.
Each test case starts with a line containing four integers, n, t, k, l, 0≤n≤1000(the number of the events), 1≤t≤100(usual time length to stay awake), 1≤k≤50(usual time length to sleep), 0≤l≤20(maximum extra time length to stay awake).
Then n lines follow, the ith line contains three integers describing the ith event, si, ei, vi, 0 ≤ si < ei ≤ 10,000(starting time and ending time), 1 ≤ vi ≤ 500(value)


Your output should be exactly c lines, each line with an integer number representing the maximum final value.

Sample Input

3 16 8 4
0 4 10
3 5 28
4 18 21
3 16 8 4
26 30 10
29 31 28
30 43 21

Sample Output



In the first case, Sleeper should stay awake for 16 time units and finish the event with value of 28 points. Choosing the first and the third event will get 10 + 21 - 2 * 2 = 27 points, which is a less effective choice.
In the second case, Sleeper should stay awake for 17 time units in the first day, and sleep 9 time units after that. Then he should participate the two events with 10 or 21 value points, staying awake for 17 time units in the second day, having a total value point of -1 + 10 + 21 - 1 = 29 points.

Author: GONG, Yuan
Submit    Status