Description

小明想买一只非常漂亮的手表，他知道价格不会超过$m$ ，但不知道手表的确切价格。

已知硬币的面值$a$ $1$ , $a$ $2$ $a$ $3$ , …, $a$$n$ 和该面值的数量$c$ $1$ , $c$ $2$ , $c$ $3$ , …, $c$$n$ ，计算可以用这些 硬币支付多少种价格$（$$1$～$m$ $）$。

Format

Input

输入包含几个测试用例。

每个测试用例的第$1$行都包含两个 整数$n$ $（$$1$$≤$$n$ $≤$$1$$0$$0$$）$、$m$ $（$$m$ $≤$$1$$0$$0$$0$$0$$0$$）$；

第$2$行包含$2$$n$ 个整数$a$ $1$ , $a$ $2$ , $a$ $3$ , …, $a$$n$ 、$c$ $1$ , $c$ $2$ , $c$ $3$ , …, $c$$n$ $（$$1$$≤$$a$$i$ $≤$$1$$0$$0$$0$$0$$0$，$1$$≤$ $≤$$1$$0$$0$$0$$）$。

在最后一个测试用例后面包含两个$0$，表示结束。

Output

对每个测试用例，都单行输出答案。

Samples

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

8
4