背包与魔法 ### 问题描述 小蓝面前有 $N$ 件物品, 其中第 $i$ 件重量是 $W_{i}$, 价值是 $V_{i}$ 。她还有一个背包, 最大承重是 $M$ 。 小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品? 特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 $K$, 同时价值秝倍。(当然小蓝也可以不使用魔法) ### 输入格式 第一行包含 3 个整数 $N 、 M$ 和 $K$ 。 以下 $N$ 行, 每行两个整数 $W_{i}$ 和 $V_{i}$ 。 ### 输出格式 一个整数代表答案。 ### 样例输入 ```text 3 10 3 5 10 4 9 3 8 ``` ### 样例输出 ```text 26 ``` ### 样例说明 选择第二件和第三件物品, 同时对第二件物品使用魔法。 ### 评测用例规模与约定 对于 $30 \\%$ 的数据, $1 \leq N, M, K \leq 100$. 对于 $100 \\%$ 的数据, $1 \leq N \leq 2000,1 \leq M, K \leq 10000,0 \leq W_{i}, V_{i} \leq 10000$.