08767. 空间站货运飞船 · 林老师的题库

题目描述

一艘货运飞船即将起飞，为空间站运送补给。飞船货舱的最大载重为 $W$ 千克。

地面共有 $n$ 件候选补给包，第 $i$ 件的质量为 $w_{i}$ 千克、科学价值为 $v_{i}$ 。每件补给包至多装载一件，装载的总质量不能超过 $W$ 。

求飞船能装载的补给包科学价值总和的最大值。

第一行两个整数 $n, W$ ，分别表示补给包总数与货舱最大载重。

接下来 $n$ 行，每行两个整数 $w_{i}, v_{i}$ ，表示第 $i$ 件补给包的质量与科学价值。

输出一行，一个整数，表示科学价值总和的最大值。

输入

输出

样例解释：装载质量 $4$ 与 $5$ 的两件，总质量 $9 \leq 9$ ，价值 $40 + 55 = 95$ ，最优。

样例解释：前两件的质量都超过 $7$ 装不进货舱，只能装第三件。

对于 $100%$ 的数据： $1 \leq n \leq 100$ ， $1 \leq W \leq 1 0^{9}$ ， $1 \leq w_{i} \leq 1 0^{9}$ ， $1 \leq v_{i} \leq 1 0^{3}$ 。

本题共 10 个测试点，每个测试点 10 分。