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

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

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

输入格式

输入包含多组测试用例。

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

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

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

输出格式

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

数据范围

$1 \le N \le 100$,
$1 \le M \le 10^5$,
$1 \le A\_i \le 10^5$,
$1 \le C\_i \le 1000$

输入用例：

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

输出用例：

8
4

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解