P10119 『STA - R4』踱步

小 X 特别喜欢安静的环境，因为那可以让他心情愉悦。 现在给出 $N$ 分钟内每分钟屋内和屋外对小 X 的心情影响值，在这 $N$ 分钟内，小 X 可以从屋内踱步到屋外或是从屋外踱步到屋内**最多共** $K$ 次。（小 X 当且仅当每分钟初进行踱步，同一时刻至多踱步一次，并且踱步的时间忽略不计。第 $1$ 分钟初不可踱步，第 $N$ 分钟初可以踱步。但是在第 $1$ 分钟初可以自由选择初始状态）。 同时，过于频繁的改变会让小 X 心情烦躁，所以如果两次踱步的间隔**小于等于** $T$ 分钟，会对小 X 的心情额外造成 $P$ 点影响。（如果此次踱步是在第 $t_a$ 分钟初，上一次踱步是在第 $t_b$ 分钟初，那么这两次踱步的时间间隔为 $t_a - t_b$ 分钟）。 小 X 想知道自己的心情最好可以是多少，即第 $N$ 分钟末小 X 心情值的最大值。 若某一时刻小 X 的心情值为 $a$，之后小 X 的心情被影响了 $b$，那么在此之后小 X 的心情值将变为 $a + b$。

无

无

**【样例 #1 解释】** 对于第 $1$ 组数据，最优方案为初始时选择在屋内，分别在第 $4, 5, 7$ 分钟初进行踱步。  其中第 $2$ 次踱步与第 $1$ 次踱步之间的间隔为 $5 - 4 = 1$ 分钟，对小 $\text{X}$ 的心情产生 $3$ 的贡献，第 $3$ 次踱步与第 $2$ 次踱步之间的间隔为 $7 - 5 = 2$ 分钟，对小 X 的心情产生 $3$ 的贡献。 因此小 X 的心情值为 $$\left(0+5+8-7+0-4-3+0\right) + 6 = 5$$ 前半部分为灰色格子的权值和，后半部分为两次频繁踱步产生的额外贡献，可以证明此方案最优。 **【样例 #2 解释】** 请注意答案可能超过 $32$ 位整型数字的范围。 **【样例 #3 解释】** 请注意答案可能为负数。 **【数据范围】** 对于 $100\%$ 的数据： - $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$。 - 保证单个测试点输入数据规模不超过 10 MB。 **本题采用捆绑测试。** |Subtask 编号|数据范围|分值|依赖子任务| |:--------:|:--------:|:--------:|:--------:| |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|无特殊限制|$30$|$1,2,3,4$|