2196: 宝典2第十一章硬币问题

【题目描述】硬币问题(coin.cpp/c/pas)HDU 2844

给你n种硬币，知道每种的面值A_i和每种的数量C_i。问能凑出多少种不大于m的面值。

【输入格式】

有多组数据，每一组第一行有两个整数 n(1≤n≤100)和m(m≤100000)，第二行有2n个整数，即面值A₁，A₂，A₃，…，A_n和数量C₁，C₂，C₃，…，C_n (1≤A_i≤100000，1≤C_i≤1000)。所有数据结束以2个0表示。

【输出格式】

每组数据输出一行答案。

【输入样例】

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

【输出样例】

8

4