Problem1079--PIPI的存钱罐

1079: PIPI的存钱罐

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 303  Solved: 200
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有n种硬币,每种硬币有特定的重量wei[i] 克和它对应的价值val[i]. 

已知有一个承重量为m的存钱罐,当里面正好装着重量为m的硬币时,问你这个存钱罐中硬币的最小价值是多少? 如果不可能存在m克的情况, 那么就输出”impossible“

Input

多组输入。
第一行包括两个整数n,m(1<=n<=500,1<=m<=10000)
接下来n行,每行两个整数v,w,表示第i中硬币的价值与重量。(1<=v<=10000,1<=w<=m)

Output

输出可能的最小价值,如果不可能存在m克的情况, 那么就输出”impossible“

Sample Input

2 100
1 1
30 50
2 100
1 1
50 30

Sample Output

60
100

Source/Category