Problem Description

Little X particularly enjoys a quiet environment, as it brings him a pleasant mood.

Given the mood impact values for each minute inside and outside the house over \( N \) minutes, Little X can stroll from inside to outside or vice versa at most \( K \) times within these \( N \) minutes. (Little X can only stroll at the beginning of each minute, no more than once per minute, and the time taken to stroll is negligible. He cannot stroll at the beginning of the 1st minute, but he can at the beginning of the \( N \)-th minute. However, he can freely choose his initial state at the beginning of the 1st minute).

Additionally, frequent changes can irritate Little X, so if the interval between two strolls is less than or equal to \( T \) minutes, it will cause an extra \( P \) points of mood impact. (If the current stroll is at the beginning of the \( t_a \)-th minute and the last stroll was at the beginning of the \( t_b \)-th minute, then the interval between these two strolls is \( t_a - t_b \) minutes).

Little X wants to know what his best possible mood can be, i.e., the maximum mood value at the end of the \( N \)-th minute.

If Little X's mood value at a certain moment is \( a \), and he experiences an impact of \( b \), then his mood value will become \( a + b \) thereafter.

Input Format

This problem contains multiple test cases within a single test point.

The first line contains two positive integers \( \text{id} \) and \( \text{TEST} \). \( \text{id} \) represents the Subtask number, and \( \text{TEST} \) represents the number of test cases. Specifically, the sample case has \( \text{id} \) as 0.

For each test case:

The first line contains four integers \( N, K, T, P \).

The next \( N \) lines each contain two integers. The \( i \)-th line contains two integers \( a_i, b_i \), representing the mood impact values for the \( i \)-th minute inside and outside the house, respectively.

Output Format

For each test case, output a single integer on a line, representing the maximum mood value at the end of the \( N \)-th minute.

Sample Input and Output

Input Sample #1

0 2
8 3 2 3
0 -2
5 -10
8 0
-10 -7
0 -3
-4 -9
-9 -3
-7 0
8 3 2 -6
9 6
9 -6
3 7
-4 3
8 -9
6 0
-10 9
-8 -4

Output Sample #1

5
36

Input Sample #2

0 1
12 3 2 -35771156
797235777 25138038
801541087 -405462832
936777370 -973167834
74493410 60154946
263320806 782480907
-940214410 805511853
806065179 463119365
-295177485 -112301429
-403964212 202831413
122359196 611468120
-555210139 549749508
793784715 -38433603

Output Sample #2

6706692096

Input Sample #3

0 1
5 2 1 -100
-44 -72
-36 -23
-4 0
-22 -1
-88 3

Output Sample #3

-65

Notes/Hints

[Sample #1 Explanation]

For the first set of data, the optimal strategy is to start inside, and stroll at the beginning of the 4th, 5th, and 7th minutes.

The interval between the 2nd and 1st strolls is \( 5 - 4 = 1 \) minute, contributing 3 points to Little X's mood, and the interval between the 3rd and 2nd strolls is \( 7 - 5 = 2 \) minutes, contributing 3 points to Little X's mood.

Thus, Little X's mood value is

\[ \left(0 + 5 + 8 - 7 + 0 - 4 - 3 + 0\right) + 6 = 5 \]

The first part is the sum of the values in the gray cells, and the second part is the extra contribution from the frequent strolls. This strategy is proven to be optimal.

[Sample #2 Explanation]

Note that the answer may exceed the range of a 32-bit integer.

[Sample #3 Explanation]

Note that the answer may be negative.

[Data Range]

For \( 100\% \) of the data:

• \( 1 \le \text{TEST} \le 10^5 \);
• \( 2 \le N \le 2 \times 10^5 \);
• \( 1 \le K \le \min\left\{200, N\right\} \);
• \( 1 \le T \le \min\left\{2 \times 10^4, N\right\} \);
• \( \left\lvert a_i \right\rvert, \left\lvert b_i \right\rvert, \left\lvert P \right\rvert \le 10^9 \);
• \( \sum N \cdot K \le 5 \times 10^7 \);
• The input data size for a single test point does not exceed 10 MB.

This problem is bundled testing.

见题面 Input 部分

见题面 Output 部分