242012 - T3-最大价值选择

题目描述

有 n 件物品,每件物品都有重量和价值。

第 i 件物品的重量为 w_i,价值为 v_i。

现在有一个容量为 W 的背包。

每件物品只能选择一次,也可以不选择。

要求在所有选中物品的重量总和不超过 W 的前提下,使物品的价值总和最大。

请输出能够获得的最大价值。

输入

第一行输入两个正整数 n,W,分别表示物品数量和背包容量。

接下来 n 行,每行输入两个正整数 w_i,v_i,分别表示第 i 件物品的重量和价值。

输出

输出一个整数,表示能够获得的最大价值。

样例

输入

4 7
2 3
3 4
4 5
5 8

输出

11
说明

样例解释

选择第 1 件和第 4 件物品:

  • 总重量:2+5=7
  • 总价值:3+8=11

满足容量限制,且总价值最大。

因此答案为 11。

数据范围

  • 1\le n\le 20
  • 1\le W\le 10^9
  • 1\le w_i,v_i\le 10^6
标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题