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


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

输入

2 6
5 10
3 1

输出

10
2
示例2

输入

3 8
3 10
9 1
10 1

输出

20
0

说明

无法恰好装满背包。
示例3

输入

6 13
13 189
17 360
19 870
14 184
6 298
16 242

输出

596
189

说明

可以装5号物品2个,达到最大价值298*2=596,若要求恰好装满,只能装1个1号物品,价值为189.
加载中...