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

Petals linger about

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

题目背景

虽然下面的代码完全正确，但是仍然差一点才可以通过此题；注意一下代码与之前的差别，这在你自己写代码时也需要考虑到。

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

#include <iostream>

using namespace std;
using ll = long long;

const int N = 45;

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


ll dfs(int idx, ll nowv, ll noww)
{
	if(nowv > m) return 0;
	if(idx == n) return noww;
	
	ll 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

样例3

输入

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

输出

5000000000

数据范围与约定

$1 \le N \le 40$

$1 \le V \le 10^9$

$1\le v_i \le V$

$1\le w_i \le 10^9$