重点词汇:

constraint  n. 限制; 束缚; 克制; 拘束;

charm  n. 魅力,魔力,护身符,咒语,小饰件; v. 吸引;迷住;

deduce v. 推断,演绎

bracelet n 手镯;

spy n. 间谍;密探; v. 突然看见,认出,查明;

题目来自:https://acs.jxnu.edu.cn/problem/NOIOPJCH02067113

Charm Bracelet

护身符手镯

 1000ms  65536K

描述：

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied

         Bessie去过珠宝购物中心商城,突然发现看一串护身符手镯                当然,她希望从N  (1 ≤ N≤ 3,402) 个可取得的护身符尽可能多的得到最好的护身符                                    在提供的列表中每一个护

list has a weight Wi(1 ≤ Wi≤ 400), a 'desirability' factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).

身符 i 都有 对应的重量Wi (1 ≤ Wi≤ 400) 以及 一个渴望值 Di (1 ≤ Di≤ 100),没一个护身符最多只能被使用一次.       Bessie只能拿总重量不超过M(1 ≤ M≤ 12,880)的护身符

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

 给出Bessie最多能拿的重量作为限制以及一列表包含重量和渴望度的护身符.                                               推算渴望度最大可能值.

输入：

Line 1: Two space-separated integers: N and M 第一行: 有两个空格分开整数: N和M;
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di 第二行: 第一行所提到的护身符 i  其中 Wi和Di用两个空格隔开;

输出：

Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints 一行: 一个整数,他是在所给总量限制下能取得的最大渴望值;