{"raw_statement":[{"iden":"statement","content":"小 X 特别喜欢安静的环境，因为那可以让他心情愉悦。\n\n现在给出 $N$ 分钟内每分钟屋内和屋外对小 X 的心情影响值，在这 $N$ 分钟内，小 X 可以从屋内踱步到屋外或是从屋外踱步到屋内**最多共** $K$ 次。（小 X 当且仅当每分钟初进行踱步，同一时刻至多踱步一次，并且踱步的时间忽略不计。第 $1$ 分钟初不可踱步，第 $N$ 分钟初可以踱步。但是在第 $1$ 分钟初可以自由选择初始状态）。\n\n同时，过于频繁的改变会让小 X 心情烦躁，所以如果两次踱步的间隔**小于等于** $T$ 分钟，会对小 X 的心情额外造成 $P$ 点影响。（如果此次踱步是在第 $t_a$ 分钟初，上一次踱步是在第 $t_b$ 分钟初，那么这两次踱步的时间间隔为 $t_a - t_b$ 分钟）。\n\n小 X 想知道自己的心情最好可以是多少，即第 $N$ 分钟末小 X 心情值的最大值。\n\n若某一时刻小 X 的心情值为 $a$，之后小 X 的心情被影响了 $b$，那么在此之后小 X 的心情值将变为 $a + b$。"},{"iden":"input","content":"**本题单个测试点内含有多组测试数据。**\n\n第一行两个正整数 $\\text{id},\\text{TEST}$。其中 $\\text{id}$ 代表 Subtask 编号，$\\text{TEST}$ 代表测试数据组数。特别的，样例的 $\\text{id}$ 为 $0$。\n\n对于每组测试数据：\n\n第一行为四个整数 $N, K, T, P$。\n\n接下来 $N$ 行每行两个整数。其中第 $i$ 行的两个整数 $a_i, b_i$ 分别代表第 $i$ 分钟屋内和屋外对小 X 心情的影响值。"},{"iden":"output","content":"对于每组测试数据，输出一行一个整数，代表第 $N$ 分钟末小 X 心情值的最大值。"},{"iden":"note","content":"**【样例 #1 解释】**\n\n对于第 $1$ 组数据，最优方案为初始时选择在屋内，分别在第 $4, 5, 7$ 分钟初进行踱步。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/cx7tr8m2.png)\n\n其中第 $2$ 次踱步与第 $1$ 次踱步之间的间隔为 $5 - 4 = 1$ 分钟，对小 $\\text{X}$ 的心情产生 $3$ 的贡献，第 $3$ 次踱步与第 $2$ 次踱步之间的间隔为 $7 - 5 = 2$ 分钟，对小 X 的心情产生 $3$ 的贡献。\n\n因此小 X 的心情值为\n\n$$\\left(0+5+8-7+0-4-3+0\\right) + 6 = 5$$\n\n前半部分为灰色格子的权值和，后半部分为两次频繁踱步产生的额外贡献，可以证明此方案最优。\n\n**【样例 #2 解释】**\n\n请注意答案可能超过 $32$ 位整型数字的范围。\n\n**【样例 #3 解释】**\n\n请注意答案可能为负数。\n\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据：\n\n- $1 \\le \\text{TEST} \\le 10^5$；\n- $2 \\le N \\le 2 \\times 10^5$；\n- $1 \\le K \\le \\min\\left\\{200, N\\right\\}$；\n- $1 \\le T \\le \\min\\left\\{2 \\times 10^4, N\\right\\}$；\n- $\\left\\lvert a_i \\right\\rvert,\\left\\lvert b_i \\right\\rvert,\\left\\lvert P \\right\\rvert \\le 10^9$。\n- $\\sum N \\cdot K \\le 5 \\times 10^7$。\n- 保证单个测试点输入数据规模不超过 10 MB。\n\n**本题采用捆绑测试。**\n\n|Subtask 编号|数据范围|分值|依赖子任务|\n|:--------:|:--------:|:--------:|:--------:|\n|1|$N \\le 20, \\text{TEST} \\le 10$|$5$||\n|2|$\\sum N^2K \\le 5 \\times 10^7$|$20$|$1$|\n|3|$K \\le 5, N \\le 5 \\times 10^4, \\text{TEST} \\le 10$|$15$||\n|4|$P=-10^9, 0 \\le \\left\\lvert a_i \\right\\rvert,\\left\\lvert b_i \\right\\rvert \\le 100$|$30$||\n|5|无特殊限制|$30$|$1,2,3,4$|"}],"translated_statement":null,"sample_group":[["0 2\n8 3 2 3\n0 -2\n5 -10\n8 0\n-10 -7\n0 -3\n-4 -9\n-9 -3\n-7 0\n8 3 2 -6\n9 6\n9 -6\n3 7\n-4 3\n8 -9\n6 0\n-10 9\n-8 -4\n","5\n36\n"],["0 1\n12 3 2 -35771156\n797235777 25138038\n801541087 -405462832\n936777370 -973167834\n74493410 60154946\n263320806 782480907\n-940214410 805511853\n806065179 463119365\n-295177485 -112301429\n-403964212 202831413\n122359196 611468120\n-555210139 549749508\n793784715 -38433603\n","6706692096\n"],["0 1\n5 2 1 -100\n-44 -72\n-36 -23\n-4 0\n-22 -1\n-88 3\n","-65\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}