题目描述

给定$\red {N}$种硬币，其中第 $\red {i }$种硬币的面值为$\red {A _i,~}$ 共有$\red {C_i~}$个。

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

求$\red {1\sim M}$之间能被拼成的面值有多少个。

输入格式

入包含多组测试用例。

每组测试用例第一行包含两个整数$\red N$和$\red M$。

第二行包含$\red {2N}$个整数，分别表示$\red {A _1~ ,A_2~ ,…,A_N~}$和$\red {C _1~ ,C _2~ ,…,C _N~ }$。

当输入用例$\red {N=0，M=0}$时，表示输入终止，且该用例无需处理。

输出格式

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

样例

输入样例

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

输出样例

8
4

提示

$\red {1≤N≤100}$,

$\red {1≤M≤10^5}$,

$\red {1≤A _i~ ≤10^5}$,

$\red {1≤C _i~ ≤1000}$