含负收益的样本筛选

题目描述

实验舱里有 $n$ 份样本待带回地球，每份样本占用体积并有科学价值，价值可能为负数（意味着占用位置却拖累任务）。背包容量为 $W$，每份样本只能取或不取。你可以选择带回零件样本或空手而归，目标是使总价值最大且体积不超过容量。请输出能获得的最大总价值。

输入格式

第一行包含两个整数 $n,W$。

接下来 $n$ 行，每行包含两个整数，表示一份样本的体积与价值。

输出格式

输出一个整数，表示可以获得的最大总价值（允许为 $0$，表示什么都不带）。

输入输出样例 #1

输入 #1

3 5
2 -3
3 4
4 -1

输出 #1

4

数据范围

对于 $100\%$ 的数据，$1 \le n \le 200$，$1 \le W \le 2000$，体积在 $[1,10^4]$，价值在 $[-10^4,10^4]$。EOF