P10119 『STA - R4』Pacing

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$.

**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$.

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

**[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 $$\left(0+5+8-7+0-4-3+0\right) + 6 = 5$$ 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.** |Subtask ID|Constraints|Points|Dependencies| |:--------:|:--------:|:--------:|:--------:| |1|$N \le 20, \text{TEST} \le 10$|$5$|| |2|$\sum N^2K \le 5 \times 10^7$|$20$|$1$| |3|$K \le 5, N \le 5 \times 10^4, \text{TEST} \le 10$|$15$|| |4|$P=-10^9, 0 \le \left\lvert a_i \right\rvert,\left\lvert b_i \right\rvert \le 100$|$30$|| |5|No special constraints|$30$|$1,2,3,4$| Translated by ChatGPT 5