Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-背包与魔法
题目 2721:

蓝桥杯2022年第十三届决赛真题-背包与魔法

时间限制: 3s 内存限制: 1024MB 提交: 228 解决: 27

题目描述

小蓝面前有 N 件物品,其中第 i 件重量是 Wi,价值是 Vi。她还有一个背包,最大承重是 M。

小蓝想知道在背包称重范围内,她最多能装总价值多少的物品?

特别值得一提的是,小蓝可以使用一个魔法,将一件物品的重量增加 K,同时价值翻倍。(当然小蓝也可以不使用魔法)

输入格式

第一行包含 3 个整数 N、M 和 K。

以下 N 行,每行两个整数 Wi 和 Vi

输出格式

一个整数代表答案。

样例输入

3 10 3
5 10
4 9
3 8

样例输出

26

提示

选择第二件和第三件物品,同时对第二件物品使用魔法。

对于 30% 的数据,1 ≤ N, M, K ≤ 100.

对于 100% 的数据,1 ≤ N ≤ 2000, 1 ≤ M, K ≤ 10000, 0 ≤ Wi , Vi ≤ 10000.

标签