1114: 硬币

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：791 Solved：339

Description

居住在Silverland 的居民只使用硬币。他们有n种价值的硬币，分别为A1、A2、A3...An的硬币，这些硬币的数量分别为C1、C2、C3...Cn。有一天Tony老师打开钱箱，发现里面有一些硬币。他决定在附近的商店买一块很好的手表，他知道价格不会超过m。

但他不知道手表的确切价格。Tony老师想知道指定数量的硬币，在不找零的情况下能支付多少种不同的价格（1到m能凑出面额的个数）？



不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

输入包含多个测试用例。

每个测试用例的第一行包含两个整数n（1<=n<=100），m（m<=100000）。

第二行包含2n个整数，表示A1、A2、A3…An、C1、C2、C3…Cn（1</=Ai<=100000，1<=Ci<=1000）。

最后一个测试用例后面跟着两个零

Output

每组测试数据输出一个数，表示在不找零的情况下能支付多少种面值

Sample Input Copy 

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

Sample Output Copy 

8
4

Source/Category