Problem Description

X really likes quiet environments, because they make him feel happy.

You are given the mood impact values of being indoors and outdoors for each minute within $N$ minutes. During these $N$ minutes, X may pace from indoors to outdoors or from outdoors to indoors at most $K$ times in total. (X paces if and only if it is at the start of a minute. At the same time, he can pace at most once, and the time spent pacing is ignored. He cannot pace at the start of minute $1$, but he can pace at the start of minute $N$. However, at the start of minute $1$, he may freely choose the initial state.)

Also, changing too frequently makes X irritated. Therefore, if the interval between two paces is less than or equal to $T$ minutes, X's mood receives an additional impact of $P$. (If this pace happens at the start of minute $t_a$, and the previous pace happens at the start of minute $t_b$, then the time interval between these two paces is $t_a - t_b$ minutes.)

X wants to know how good his mood can be, i.e., the maximum possible mood value at the end of minute $N$.

If at some moment X's mood value is $a$, and afterwards his mood is affected by $b$, then his mood value becomes $a + b$.

Input Format

This problem contains multiple groups of testdata within a single test point.

The first line contains two positive integers $\text{id},\text{TEST}$. Here $\text{id}$ is the Subtask ID, and $\text{TEST}$ is the number of testdata groups. In particular, in the samples, $\text{id}$ is $0$.

For each group of testdata:

The first line contains four integers $N, K, T, P$.

The next $N$ lines each contain two integers. On line $i$, the two integers $a_i, b_i$ represent the mood impact values of being indoors and outdoors, respectively, during minute $i$.

Output Format

For each group of testdata, output one integer per line, representing the maximum mood value at the end of minute $N$.

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

5
36

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

6706692096

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

-65

Hint

[Sample #1 Explanation]

For the first group of data, the optimal plan is to start indoors, and pace at the start of minutes $4, 5, 7$.

The interval between the 2nd pace and the 1st pace is $5 - 4 = 1$ minute, contributing $3$ to X's mood. The interval between the 3rd pace and the 2nd pace is $7 - 5 = 2$ minutes, contributing $3$ to X's mood.

Therefore, X's mood value is

The first part is the sum of the weights of the gray cells, and the second part is the extra contribution caused by two frequent paces. It can be proven that this plan is optimal.

[Sample #2 Explanation]

Please note that the answer may exceed the range of 32-bit integers.

[Sample #3 Explanation]

Please note that the answer may be negative.

[Constraints]

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$.
• It is guaranteed that the input size of a single test point does not exceed 10 MB.

This problem uses bundled tests.

Translated by ChatGPT 5