题目描述

HDU 2844

给你$\red{n}$种硬币，知道每种的面值$\red{Ai}$和每种的数量$\red{Ci}$。问能凑出多少种不. 大于$\red{m}$的面值。.

输入格式

有多组数据,每一组第一行有两个整数$\red{n(1≤}$$\red{n≤}$$\red{100)}$和$\red{m( m≤}$$\red{100 000),}$第二 行有$\red{2n}$个整数,即面值$\red{A1,A2,A3,...,An}$和数量$\red{Cl,C2,C3,...,Cn (1≤}$$\red{Ai≤}$$\red{100 000,}$ $\red{1≤}$$\red{Ci≤}$$\red{1000)}$。所有数据结束以$\red{2}$个$\red{0}$表示。

输出格式

每组数据输出一行答案。

样例

输入样例

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

输出样例

8
4