A5075 | $午枫爱搬家2$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

小午和小枫又在搬家，他们有 $n$ 件物品需要搬运，每件物品的体积为 $w_i$ ，价值为 $v_i$ 。 他们租了一辆能容纳 $m$ 体积物品的卡车，他们想在不超过卡车容积的情况下，搬运价值总和尽量高的物品。 求他们在搬运的物品未超过卡车容量的情况下能得到的最大价值是多少。

第一行输入两个正整数 $n,m$ $(1\leq n\leq 5000,1\leq m\leq 20000)$ ，分别表示物品数量以及卡车容量。 接下来 $n$ 行，每行两个正整数 $w_i,v_i$ $(1\leq w_i\leq 20000,1\leq v_i\leq 10^9)$ ，分别表示第 $i$ 个物品的体积以及价值。

输出一个整数，表示在搬运的物品未超过卡车容量的情况下得到的最大价值。

输入 #1

输出 #1

C++ 编辑器

输入

输出