08758. 航模社的工具包 · 林老师的题库

题目描述

航模社周末去郊外参加飞行活动，每名队员只能随身携带一个统一发放的工具包，工具包的最大承重为 $W$ 克。社里共有 $n$ 件公用工具与备件可供携带，第 $i$ 件重 $w_{i}$ 克，带上它对当天飞行活动的帮助评分为 $d_{i}$ 分。每件工具最多带一件。

在携带工具总重不超过 $W$ 克的前提下，帮助评分总和最大是多少？

第一行两个整数 $n$ 和 $W$ ，表示工具件数与工具包最大承重（克）。

接下来 $n$ 行，第 $i$ 行两个整数 $w_{i}$ 和 $d_{i}$ ，表示第 $i$ 件工具的重量与帮助评分。

一行一个整数，表示总重不超过 $W$ 克时帮助评分总和的最大值。

输入

输出

样例解释：携带第 $4$ 、 $3$ 件工具，总重 $400 + 200 = 600$ 克，恰好达到承重上限，帮助评分 $300 + 150 = 450$ 分；其余方案的评分都不超过 $450$ 分。

样例解释：只有一件工具，重量恰好等于承重 $800$ 克，可以携带，评分 $260$ 分。

对于 $100%$ 的数据： $1 \leq n \leq 100$ ， $0 \leq W \leq 1 0^{4}$ ， $1 \leq w_{i} \leq 900$ ， $1 \leq d_{i} \leq 500$ 。

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