【例题4】硬币方案

题目描述

给定$N$种硬币，其中第$i$种硬币的面值为$a_{i}$，共有$C_{i}$个。从中选出若干个硬币，把面值相加，若结果为$S$，则称“面值$S$能被拼成”。求$1$到$M$之间能被拼成的面值有多少个。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数$N$和$M$。

第二行包含$2N$个整数，分别表示$a_{1}$,$a_{2}$,$\ldots$,$a_{N}$和$c_{1}$,$c_{2}$,$\ldots$,$c_{N}$。

当输入$N=0$,$M=0$时，表示输入终止，且该数据无需处理。

输出格式

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

数据范围与提示

对于$100\%$的数据，$1 \leq N \leq 100$，$1 \leq M \leq 10^{5}$，$1 \leq a_{i} \leq 10^{5}$，$1 \leq c_{i} \leq 1000$。

样例

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

8
4