题目描述

给定 $N$ 种硬币，其中第$i$ 种硬币的面值为$A_i$，共有$C_i$ 个。

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

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

输入格式

输入包含多组测试用例。

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

第二行包含 2$N$ 个整数，分别表示 $A_1,A_2,…,A_N$ 和 $C_1,C_2,…,C_N$。

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

输出格式

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

用例

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

8
4

数据范围

$1≤N≤100, 1≤M≤10^5, 1≤A_i≤10^5, 1≤C_i≤1000$

来源

• POJ1742
• HDU2844
• 算法竞赛进阶指南