你有一个背包，最多能容纳的体积是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)空间复杂度
加载中...