组装零件

天码破译了，但Zero的核心是一个机器——需要组装零件。

"零件？"CC问。

"对。"你说，"$n$个零件，每个有一个体积$v_i$和价值$w_i$。背包容量$V$，求最大价值。"

"背包？"

"完全背包。"你说，"每种零件可以选无限次。"

"无限？"

"对。"你说，"只要容量够，可以一直选。"

"咋选？"

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

"转移？"

"正序更新。"你说，"$dp[j]=\max(dp[j],dp[j-v_i]+w_i)$。"

"正序？"

"对。"你说，"因为可以重复选，所以要正序——让后面的状态可以用到前面的更新。"

"第47个零件。"你说，"$v_{47}=47$，$w_{47}=47$。"

"性价比1。"

"对。"你说，"不高不低，但可选。"

"选多少次？"

"看容量。"你说，"如果$V=100$，最多选2次（$2\times 47=94$）。"

"剩6容量？"

"选别的。"你说，"或者空着——不是所有容量都要用完。"

CC看着那些零件——像积木，像石头，像某种可以拼成东西的碎片。

"能拼成啥？"她问。

"看设计图。"你说，"设计图决定了需要哪些零件。"

"设计图是啥？"

"目标。"你说，"我们要最大化的价值。"

"价值是啥？"

"看定义。"你说，"每个零件有自己的价值，我们选总价值最大的组合。"

Echo把组装过程投射出来——零件一个一个放进去，背包慢慢填满。

"以前我觉得装不满。"她说，"现在……刚刚好。"

"因为你在选。"CC说。

"对。"Echo说，"因为我在选。"

题目描述

$n$种零件，每种体积$v_i$，价值$w_i$。背包容量$V$，每种可选无限次。求最大价值。

输入格式

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

输出格式

最大价值。

输入样例

5

输出样例

0

提示

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