硬币问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

现在有一些硬币,将这些硬币按面值分组可以分为n组,第i组的面值为Ai,数量为Ci,现在问这些硬币可以组成多少种不超过总价值不超过m的支付方式。

Input

 

多组输入。

对于每组数据,第一行为两个整数n,m1 <= n <= 100,1 <= m <= 100000) 。

接下来的一行有n个整数Ai,n个整数Ci1 <= Ai <= 10000,1 <= Ci <= 1000) 。

文件的最后一行为两个0,代表输入结束。

Output

 

对于每组数据,输出一行,包含一个整数代表答案。

Sample Input

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

Sample Output

8
4

Hint

 

Source