304006 - 硬币问题

给你n种硬币,知道每种硬币的面值Ai和每种的数量Ci。问能凑出多少种不大于m的面值。

输入

有多组数据,每一组第一行有两个整数 n(1\le n\le100)m(m\le100000),第二行有2n个整数,即面值A_1,A_2,A_3,…,A_n和数量C_1,C_2,C_3,…,C_n(1\le A_i\le100000,1\le C_i\le1000)。所有数据结束以2个0表示。

输出

每组数据输出一行答案。

样例

输入

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

输出

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