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 ≤100000$，$1≤c_i≤1000$）。

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

Output

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

Samples

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

8
4

来源

HDU2844