SP28600 BDOI16D - One Punch Man

一拳超人 ============= 埼玉是最强的超级英雄。他通过艰苦的训练，达到了常人无法企及的超人状态。然而，这也让他失去了挑战感，因为他面对的每一个怪物都能被他一拳击败。 在一条直线上分布着 $N$ 组怪物，第 $i$ 组怪物距离直线起点的距离为 $X_i$，每组怪物有 $V_i$ 个成员。当埼玉在某一点 $P$ 打拳时，所有在距离 $P$ 的 $R$ 范围内的怪物（即从 $P-R$ 到 $P+R$，包括边界点）都会被冲击波消灭。由于完成了这些英雄任务感到疲惫，埼玉最多可以出拳 $K$ 次。你能帮助他计算一下，最多能消灭多少个怪物吗？ **输入格式：** 第一行是测试用例的个数 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含三个整数 $N$、$R$ 和 $K$。接下来的 $N$ 行，每行包含两个整数，分别表示怪物组的位置 $X_i$ 和怪物的数量 $V_i$。 **数据范围与提示：** - $1 \le T \le 5$ - $1 \le N \le 10^5$ - $1 \le V_i \le 10^4$ - $1 \le K \le 10^4$ 针对简单版本： - $0 \le R, X_i \le 10^4$ 针对困难版本： - $0 \le R, X_i \le 10^8$ **输出格式：** 对于每个测试用例，输出一行 `"Case t: m"`，其中 $t$ 是测试用例编号，$m$ 是埼玉最多可以消灭的怪物数量。 **样例输入：** ``` 2 4 3 1 6 10 12 110 19 100 24 30 5 3 2 3 3 5 2 3 8 10 5 0 5 ``` **样例输出：** ``` Case 1: 130 Case 2: 23 ``` **样例解释：** 在样例 1 中，埼玉可以选择在位置 21 或 22 打拳，这样可以消灭 130 个怪物。如果选择在位置 21 打拳，冲击波的范围为 18 到 24，能够消灭 19 号位置和 24 号位置的所有怪物。同理，如果选择在位置 22 打拳，范围将是 19 到 25。在其他任何位置打拳都无法消灭更多的怪物。 在样例 2 中，埼玉可以通过两次打拳消灭掉所有的怪物。 **题目作者：Moinul Shaon** **本翻译由 AI 自动生成**

无

无