炼金术师的素材包

题目描述

天才炼金术师艾莉丝最近获得了一个神奇的“虚空背包”，这个背包的总承重上限为 $M$。

为了进行一次伟大的炼金实验，艾莉丝准备前往“元素森林”收集素材。森林里共有 $N$ 种不同的炼金素材，每种素材都有无限多份。第 $i$ 种素材的单个重量为 $w_i$，能够提供的炼金能量值为 $v_i$。

艾莉丝希望在她背包能够承载的重量范围内，尽可能多地收集素材，以获得最高的能量总和。每种素材她可以挑选任意多份（包括 0 份）。

你能帮艾莉丝计算出，她最多能获得多少炼金能量吗？

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示素材的种类数和背包的承重上限。

接下来的 $N$ 行，每行包含两个整数 $w_i$ 和 $v_i$，分别表示第 $i$ 种素材的重量和能量值。

输出格式

输出一个整数，表示能够获得的最大能量总和。

输入输出样例 #1

输入 #1

2 10
3 5
4 7

输出 #1

17

样例 1 说明

选择两份重量为 3 的素材和一份重量为 4 的素材，总重量为 $3 \times 2 + 4 = 10$，总能量为 $5 \times 2 + 7 = 17$。

输入输出样例 #2

输入 #2

3 15
4 10
5 12
7 20

输出 #2

40

数据范围

对于 $60\%$ 的数据，$1 \le N, M \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 10^4$，$1 \le M \le 10^4$，$1 \le w_i \le M$，$1 \le v_i \le 10^6$。 注意：结果可能很大，请使用合适的数据类型。

建议

一刷