题目分析
本题是一个任务排序问题，需要合理安排任务完成顺序，使得最终获得的经验值最大化。关键在于利用低等级时完成高难度任务的经验倍率奖励。

---

算法思路

核心思想：贪心排序 + 背包DP

关键观察：

• 当等级 $L < d$ 时完成任务，获得 $c \cdot x$ 经验
• 当等级 $L \geq d$ 时完成任务，获得 $x$ 经验
• 因此，在低等级时完成高难度任务能获得额外 $(c-1) \cdot x$ 的奖励经验

---

数学建模

1. 经验计算

设 $S = \sum_{i=1}^n x_i$ 为所有任务基础经验总和。

如果任务 $i$ 在等级不足时完成，获得额外经验为：

$$\text{bonus} = (c-1) \cdot x_i$$

2. 等级约束

完成一个任务 $i$ 时，如果当前经验为 $E$，等级 $L = \lfloor E/v \rfloor$。

要在 $L < d_i$ 时完成任务 $i$，需要满足：

$$E < v \cdot d_i$$

此时获得经验：$c \cdot x_i$

3. 贪心策略

定义关键值：

$$g_i = v \cdot d_i + c \cdot x_i$$

按 $g_i$ 升序排序任务，优先完成 $g_i$ 小的任务。

---

算法实现

步骤1：输入与预处理

scanf("%d%d%d", &n, &v, &c);
FOR(i, 1, n) {
    scanf("%d%d", &x[i], &d[i]);
    A += x[i];  // 基础经验总和
    g[i] = v * d[i] + c * x[i];  // 排序关键值
}

步骤2：任务排序

sort(o + 1, o + n + 1, [](int i, int j) {
    return g[i] < g[j];
});

步骤3：动态规划计算最大奖励经验

f[0] = 1;  // bitset初始化，f[i]表示能否获得i点奖励经验
FOR(i, 1, n) {
    int u = o[i];
    int y = max(M - (v * d[u] - 1) / c - 1, 0);
    f |= f << y >> y << x[u];
}

DP状态转移：

• f << y >> y：确保在满足等级约束的条件下转移
• f << x[u]：选择任务u获得 $x_u$ 点基础经验

步骤4：输出结果

ROF(i, M - 1, 0) if (f[i]) {
    cout << A + i*(c - 1) << '\n';
    break;
}

最终经验 = 基础经验总和 + 最大奖励经验

---

关键技术与优化

1. Bitset优化

bitset<M> f;

• 压缩状态存储空间
• 利用位运算加速状态转移
• 复杂度 $O(n \cdot M / w)$，其中 $w$ 为机器字长

2. 排序贪心

按 $g_i = v \cdot d_i + c \cdot x_i$ 排序，保证在满足等级约束的前提下最大化奖励经验。

3. 边界处理

int y = max(M - (v * d[u] - 1) / c - 1, 0);

确保DP转移时不会越界。

---

复杂度分析

• 时间复杂度：$O(n \cdot M / 64)$，其中 $M \approx 4 \times 10^6$
• 空间复杂度：$O(M)$
• 对于 $n \leq 2000$ 的数据范围完全可行

---

样例验证

输入：

3 10 2
15 1
2 2  
9 1

计算过程：

• 基础经验总和 $A = 15 + 2 + 9 = 26$
• 排序后确定最优完成顺序
• 最大奖励经验为 $17$
• 最终经验：$26 + 17 = 43$

输出：43

---

算法优势

1. 正确性保证：基于严谨的数学推导和贪心策略
2. 高效实现：Bitset优化大幅提升DP效率
3. 代码简洁：核心逻辑清晰，易于理解
4. 边界鲁棒：妥善处理各种极端情况

该算法通过巧妙的贪心排序和高效的动态规划，解决了任务调度中的经验最大化问题。