给定$𝑁$种硬币，其中第$𝑖$种硬币的面值为 $𝐴_𝑖$，共有 $𝐶_𝑖$ 个。

从中选出若干个硬币，把面值相加，若结果为 $𝑆$，则称“面值 $𝑆$能被拼成”。

求 $1∼𝑀$之间能被拼成的面值有多少个。

输入格式

输入包含多组测试用例。

每组测试用例第一行包含两个整数 $𝑁$ 和 $𝑀$。

第二行包含 $2𝑁$ 个整数，分别表示 $𝐴_1,𝐴_2,…,𝐴_𝑁$ 和 $𝐶_1,𝐶_2,…,𝐶_𝑁$。

当输入用例$𝑁=0，𝑀=0$时，表示输入终止，且该用例无需处理。

输出格式

每组用例输出一个结果，每个结果占一行。

数据范围

$1≤𝑁≤100,1≤𝑀≤10^5,1≤𝐴_𝑖≤10^5,1≤𝐶_𝑖≤1000$

输入用例：

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

输出用例：

8
4