84438 - 正好装满的背包问题Ⅱ

n个物品,需要用它们正好装满容量为C的背包,每个物品有无限个。

i个物品的价值为v_i,占用的背包的空间为w_i

求最大和最小总价值。如果无论如何不能正好装满背包,那么输出impossible

输入

第一行包含两个数字n,C

接下来n行,每行两个数字w_i、v_i,分别表示物品占用的空间和物品的价值。

输出

输出最大和最小总价值。如果不能正好装满背包,那么输出impossible

样例

输入

4 10
2 5
4 6
4 7
2 3

输出

25 15

输入

4 20
8 5
9 6
11 7
12 3

输出

impossible

提示

1 \leq n \leq 200 , 1 \leq C \leq 10^5 ,1 \leq wi \leq C, |vi| \leq 10^5

来源

原创

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题