洛谷P10973 Coins

//经典多重背包动态规划题

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int used[N];
int f[N],a[N],c[N];
int n,m;
int main()
{
    while(cin>>n>>m && (n || m))
    {
        memset(f,0,sizeof f);f[0]=1;
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1;i<=n;++i) cin>>c[i];
        for(int i=1;i<=n;++i)
        {
            memset(used,0,sizeof used);
            for(int j=a[i];j<=m;++j)
            {
                if(!f[j] && f[j-a[i]] && used[j-a[i]]<c[i])
                {
                    f[j]=1;
                    used[j]=used[j-a[i]]+1;
                }
            }
        }
        int maxx=0;
        for(int i=1;i<=m;++i)
            maxx+=f[i];
        cout<<maxx<<endl;
    }
    return 0;
}