该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Seeds bear new life when flowers dare to fade

这是背包问题的第二题，这三题的差别在于只有数据范围是不同的。

题目背景

虽然下面的代码完全正确，但是提交下面的代码并不会让你通过本题；不过在你进一步了解动态规划后，你可以比较他们之间的差异。

当然你也可以用下面的代码进行对拍（即用你的代码和下面代码跑同样的数据，看结果是否一致）

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N];

int dfs(int idx, int nowv, int noww)
{
	if(nowv > m) return 0;
	if(idx == n) return noww;
	
	int ans = 0;
	ans = max(ans, dfs(idx + 1, nowv + v[idx], noww + w[idx]));
	ans = max(ans, dfs(idx + 1, nowv, noww));
	
	return ans;
}

int main()
{
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++)
		cin >> v[i] >> w[i];
	
	cout << dfs(0, 0, 0) << "\n";
	
	return 0;
}

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

输入描述

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出描述

输出一个整数，表示最大价值。

样例1

输入

3 8
3 30
4 50
5 60

输出

90

样例1解释

选取第一件物品和第三件物品可以获得最大价值30+60=90.

样例2

输入

6 15
6 5
5 6
6 4
6 6
3 5
7 2

输出

17

数据范围与约定

$1 \le N \le 100$

$1 \le V \le 10^9$

$1\le v_i \le V$

$1\le w_i \le 1000$