题目描述

金银岛上的人使用金币，每种金币面值分别是 A1; A2; A3; ...; An 元。一天 Tony 决定在附近商店买一个非常好的表，他想在付钱的时候不要找零，但是他发现他的钱包里每种金币的数量分别只有 C1; C2; C3;  ... ; Cn 个。不过，Tony 知道这块表的价格不会超过 M 元金币（他不知道表的精确价格）。不知他的付钱方式能否实现。
你的任务是帮助 Tony 算一下，在 1 ...M 元范围内（包括边界），他钱包中的金币可以精确支付多少种价格。

输入格式

输入包括多组测试数据。每组测试数据的格式如下：
第一行包括 2 个整数 n; M。
第二行包括 2n 个整数 A1; A2; A3;  ...; An 和 C1; C2; C3; ...; Cn。
测试数据的最后一行有 2 个 0，这一行无需处理。

输出格式

每组测试数据输出一行，为一个整数，即能精确支付的价格种数。

样例数据

input

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

output

8
4

数据规模

对于 30% 的数据，1<=N<=30; 1<= M<=1000
对于 60% 的数据，1<=N<=60
对于 100% 的数据，1<=n<=100; 1<=M<=10^5;1<=Ai<=10^5;1<=Ci<=1000