题目描述

银地（Silverland）的人们使用硬币作为货币，硬币的面值分别为A₁、A₂、A₃……Aₙ银地元。一天，托尼打开他的存钱罐，发现里面有一些硬币。他打算在附近的商店买一块非常漂亮的手表，想要恰好支付手表的价格（不需要找零），并且他知道手表的价格不会超过m银地元，但他不清楚手表的具体价格。

请你编写一个程序，读取输入的 $n、m、A₁\sim Aₙ$（硬币面值）以及 $C₁\sim Cₙ$（对应面值硬币的数量），计算出托尼用这些硬币能够恰好支付的价格有多少种（价格范围从1到m）。

输入格式

输入包含多组测试用例。每组测试用例的第一行包含两个整数n（1≤n≤100）和m（m≤100000）；第二行包含2n个整数，分别表示A₁、A₂、A₃……Aₙ（硬币面值）和C₁、C₂、C₃……Cₙ（对应面值硬币的数量），其中1≤Aᵢ≤100000，1≤Cᵢ≤1000；最后一组测试用例后跟着两个0，表示输入结束。

输出格式

对于每组测试用例，在单独一行输出答案（即托尼能恰好支付的1~m范围内的价格种数）。

样例输入

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

样例输出

8
4

题目来源

POJ-1742