你有一个背包,最多能容纳的体积是V。 现在有n个物品,第i个物品的体积为 ,价值为。 (1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满,求至多能装多大价值的物品?
输入描述:
第一行两个整数n和V,表示物品个数和背包体积。接下来n行,每行两个数和,表示第i个物品的体积和价值。


输出描述:
输出有两行,第一行输出第一问的答案,第二行输出第二问的答案,如果无解请输出0。
示例1

输入

3 5
2 10
4 5
1 4

输出

14
9

说明

装第一个和第三个物品时总价值最大,但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。 
示例2

输入

3 8
12 6
11 8
6 8

输出

8
0

说明

装第三个物品时总价值最大但是不满,装满背包无解。 

备注:
要求O(nV)的时间复杂度,O(V)空间复杂度
加载中...