P8136 [ICPC 2020 WF] Quests

ICPC2020 WF I

为了在参加 ICPC 世界总决赛前放松一下，你决定玩一款名为 *Quests* 的电脑游戏。你已经玩过很多次了，现在你想要实现完美通关——为总决赛的完美表现做准备！ 在游戏中，你需要完成多个任务，并且每完成一个任务都会获得经验值（XP）。你在任何时候获得的总 XP 数量决定了你的当前等级。每当你获得 $v$ 个 XP 时，你就能达到一个新的等级。正式地说，你在任何时候的等级是最大的整数 $L$，使得你至少有 $L \cdot v$ 个 XP。 每个任务都有一个 XP 数量 $x$ 和一个目标难度等级 $d$。如果你在等级至少为 $d$ 时完成任务，你将获得 $x$ 个 XP。然而，如果你在等级低于 $d$ 时完成任务，你将获得 $c \cdot x$ 个 XP。常数 $c$ 是一个 XP 倍增器，当你在低于推荐等级 $d$ 时完成任务时会获得奖励。 你已经熟记所有 $n$ 个任务及其各自的 $x$ 和 $d$ 数字（你也知道数字 $v$ 和 $c$——你玩这个游戏很多次了）。你也有足够的技巧来完成任何任务，无论其目标难度等级和你的等级如何。你想要以一种能让你获得最大可能 XP 的顺序完成所有任务。 例如，在示例输入中，你能获得的最大 XP 是 43，具体如下。首先完成第二个任务（你获得 4 个 XP，因为你在等级 0 时完成了一个目标难度等级为 2 的任务）。然后完成第一个任务（你获得 30 个 XP，因为你仍然在等级 0，目标难度等级为 1）。有了 34 个 XP，你现在是等级 3。最后，完成第三个任务（你获得 9 个 XP，没有倍增器，因为你已经在等级 3）。

输入的第一行包含三个整数 $n$、$v$ 和 $c$，其中 $n$ $(1 \leq n \leq 2\,000)$ 是游戏中的任务数量，$v$ $(1 \leq v \leq 2\,000)$ 是达到每个等级所需的 XP 数量，$c$ $(2 \leq c \leq 2\,000)$ 是在达到目标难度等级之前完成任务的 XP 倍增器。 接下来是 $n$ 行，每行包含两个整数 $x$ 和 $d$ 描述一个任务，其中 $x$ $(1 \leq x \leq 2\,000)$ 是如果你在或高于其目标难度等级时完成该任务所获得的 XP 数量，$d$ $(1 \leq d_i \leq 10^6)$ 是该任务的目标难度等级。

输出通过完成所有任务可以获得的最大可能 XP 数量。

题面翻译由 ChatGPT-4o 提供。