P029 0-1 背包

题目描述

n 件物品，第 i 件的重量 wi、价值 vi。背包容量 C。
每件物品最多选 0 或 1 次，求最大总价值。

输入格式

第一行 n, C。
接下来 n 行，每行 wi, vi。

输出格式

一个整数，最大价值。

样例

输入:
4 5
1 2
2 4
3 4
4 5

输出: 8