题目描述

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。

第 $i$ 种物品的价值是 $w_i$，体积是 $v_i$。

请你选择一些物品装入背包，使得这些物品的 总体积不超过背包容量，且总价值最大

其中 总体积 的计算方法如下：

• 1、给定一个阈值 $k$
• 2、如果装入的物品中，没有一个物品的体积达到 $k$ 或更大，那么总体积就是装入物品的体积和
• 3、如果装入的物品中，存在某个物品 $i$ 的体积达到了 $k$ 或更大，那么总体积是以下两个部分之和
  • 第一部分：物品 $i$ 的体积
  • 第二部分：物品 $i$ 之外的其他物品的体积和 $\times 0.8$，保证每个物品的体积都是 $5$ 的倍数

请你计算最大价值

输入格式

第一行 $3$ 个整数，$N, V, k$，用空格隔开，分别表示物品数量和背包容积和体积阈值

接下来有 $N$ 行，每行两个整数 $w_i, v_i$，用空格隔开，分别表示第 $i$ 件物品的价值和体积。

输出格式

输出最大价值

3 53 25
100 25
20 5
40 10

240

4 45 21
4 10
1 20
2 20
2 20

16

提示

【样例 1 解释】

• 可以选择 $(100, 25), (100, 25), (40, 10)$ 这个 $3$ 个物品
• 总体积是：$25 + 25 \times 0.8 + 10 \times 0.8 = 53$
• 总价值：$100 + 100 + 40 = 240$

【样例 2 解释】

• 可以选择 4 个 $(4, 10)$

【数据范围】

对于所有测试数据，均有：

• $1 \le N \le 100, 1 \le V \le 1000$
• $1 \le w_i, v_i, k\le 1000$
• 保证所有测试用例中 $n$ 的总和不超过 $5\cdot 10^5$

特殊性质 A：$k > max\{v_i\}$，也就是说：问题是纯完全背包

来源