选购装备

开关拨完了，但你们还需要装备——进入Zero核心深处的装备。

"装备？"CC问。

"对。"你说，"给定$n$种装备，每种有重量$w_i$和价值$v_i$。背包容量为$m$，求最大价值。"

"背包？"

"01背包。"你说，"每种装备只能选一次。"

"咋选？"

"动态规划。"你说，"$dp[j]$表示容量为$j$时的最大价值。"

"转移？"

"对每种装备，倒序更新$dp$。"你说，"$dp[j]=\max(dp[j],dp[j-w_i]+v_i)$。"

"倒序？"

"对。"你说，"正序会重复选，倒序保证每种只选一次。"

"第47件装备。"你说，"$w_{47}=47$，$v_{47}=47$——重量等于价值。"

"选不选？"

"看容量。"你说，"如果容量够，选——因为价值密度是1。"

"如果不够？"

"不选。"你说，"选不了的不能硬塞。"

CC看着装备列表——像菜单，像库存，像某种选择的集合。

"选哪个？"她问。

"看性价比。"你说，"价值除以重量，越高越好。"

"47那件？"

"性价比1。"你说，"不高不低。"

"那选不选？"

"看整体。"你说，"不是单看一件，是看组合。"

"组合？"

"对。"你说，"有些装备单独不好，但组合起来好。"

"像人。"CC说，"有些人单独不行，但一起就行。"

Echo看着CC——金属身体，但说的话越来越像人了。

"你在说我？"Echo问。

"在说我。"CC说，"我一个人不行。和你们一起，就行了。"

题目描述

$n$种物品，每种有重量$w_i$和价值$v_i$。背包容量$m$，每种物品只能选一次。求最大价值。

输入格式

第一行$n$和$m$。接下来$n$行，每行$w_i$和$v_i$。

输出格式

最大价值。

输入样例

16 2
467 334
1401 1002
962 464
145 281
961 491
942 827
1574 1079
292 382
716 718
447 726
538 869
1700 1599
703 811
333 673
3393 2983
4647 3829
757 37 859 723 1741 1529 778 316 1035 190 1842 288 106 1040 942 1264

输出样例

2 143

提示

• 01背包：$dp[j]=\max(dp[j],dp[j-w_i]+v_i)$，$j$倒序。
• 时间复杂度$O(nm)$。