题目描述

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

输出格式

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

样例

输入样例：

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

输出样例：

8
4

样例解释

第一组数据：$N=3, M=10$

面值和数量：

• 面值 1，数量 2
• 面值 2，数量 1
• 面值 4，数量 1

能拼出的面值（1~10）： 1,2,3,4,5,6,7,8 共 8 个（9 和 10 不能拼出）。

第二组数据：$N=2, M=5$

面值和数量：

• 面值 1，数量 2
• 面值 4，数量 1

能拼出的面值：1,2,4,5 共 4 个（3 不能拼出）。

数据范围

• $1 \le N \le 100$
• $1 \le M \le 10^5$
• $1 \le A_i \le 10^5$
• $1 \le C_i \le 1000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB