题目

Description

Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.

You are to write a program which reads n,m,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input

The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.

Output

For each test case output the answer on a single line.

Sample Input

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

Sample Output

8
4

翻译

背景

武汉大学的 ACMer 喜欢用硬币,他们有不同价值的 A1 、 A2 、 A3 的硬币.
一天, Hibix 想用他的前买个表,他只知道可以正好用自己的硬币在不超过 m 元的情况下买下这个表,但是他忘记了表的价格
你要写一个程序读入硬币的价值 A1 、 A2 、 A3 …… 和硬币的数量 C1 、 C2 、 C3 ……计算出 Hibix 能用自己的硬币组成多少不同的钱数

输入

输入包括多组数据
每组数据先输入 n 和 m 分别表示硬币的种类数和最多的钱数( n<=100 m<=100000 )
接下来一行有 2n 个数, A1 、 A2 …… An 和 C1 、 C2 …… Cn 分别表示硬币 i 的价值和数量

输出

对于每组数据在一行里输出答案

题解

>多重背包问题<

直接套用模板即可
用 dp[i] 表示在钱数最多为 i 的情况下,能拼成的最大钱数

整个计算完成后,循环一遍得出不同的数据数,也即种类数

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 105;
const int maxm = 100005;
int v;
int dp[maxm];

void ZeroOnePack(int cost,int weight) {
    for(int i = v; i >= cost; i--)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}


void CompletePack(int cost,int weight) {
    for(int i = cost; i <= v; i++)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}


void MultiplePack(int cost,int weight,int n) {
    if(cost * n > v) {
        CompletePack(cost,weight);
    } else {
        int k = 1;
        while(k < n) {
            ZeroOnePack(cost * k,weight * k);
            n -= k;
            k *= 2;
        }
        ZeroOnePack(cost * n,weight * n);
    }
}
int value[maxn];
int number[maxn];

bool Do() {
    int n,m;
    scanf("%d%d",&n,&m);
    if(n == 0 && m == 0)
        return false;

    for(int i = 1;i <= n;i++)
        scanf("%d",&value[i]);
    for(int i = 1;i <= n;i++)
        scanf("%d",&number[i]);

    v = m;
    memset(dp,0,sizeof(dp));

    for(int i = 1;i <= n;i++) {
        MultiplePack(value[i],value[i],number[i]);
    }
    int cnt = 0;
    for(int i = 1;i <= m;i++) {
        if(dp[i] != dp[i - 1])
            cnt++;
    }

    printf("%d\n",cnt);
    return true;
}

int main() {
    while(Do());
    return 0;
}