[R38E]乘积背包 - 代码源竞赛平台

时空限制

1S/512M

题目描述

jiangly 去购物，他带了一个具有魔法属性的背包。商店里有 $n$ 个物品。

该背包对于物品体积的计算方式与众不同：

• 背包的基础占用体积为 $1$（即使不放任何物品）。
• 如果放入 $k$ 个物品，体积分别为 $w_1, w_2, \dots, w_k$，则总占用体积为 $1 \times w_1 \times w_2 \times \dots \times w_k$。

每个物品都有一个价值 $v_i$。jiangly 希望在背包总占用体积不超过 $X$ 的前提下，使得放入背包的物品价值之和最大。

格式

输入格式

第一行包含两个整数 $n, X$，分别表示物品数量和背包的最大容量。

接下来 $n$ 行，每行包含两个整数 $w_i, v_i$，分别表示第 $i$ 个物品的体积和价值。

输出格式

输出一个整数，表示满足条件的最大价值和。

样例

样例输入 #1

4 10
5 6
3 2
2 4
1 6

样例输出 #1

16

样例解释 #1

对于第一个样例，可以选择第 $1, 3, 4$ 个物品。 体积占用为 $1 \times 5 \times 2 \times 1 = 10 \le 10$。 价值和为 $6 + 4 + 6 = 16$。

样例输入 #2

6 1000000000
998244353 1
998244353 1
998244353 1
998244353 1
998244353 1
998244353 1

样例输出 #2

1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$X\le$
$1$	$20$	$20$	$10^9$
$2$	$30$	$100$	$5\times 10^5$
$3$	$30$	$200$	$10^9$
$4$	$20$	$2000$

对于 $100\%$ 的数据，$1\leq n \leq 2000$，$1\leq v_i \leq 2000$，$1\leq w_i \leq X$，$1\leq X \leq 10^9$。