poj 1742 Coins

// v给出N种硬币和个数,问可以取到1->M中的多少个值。
// 背包 完全背包 或多 重背包(二进制优化)都可以做
// 
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MOD 1000000007
#define maxn 100010
int dp[maxn],use[maxn];
int val[110],num[110];
int main(){

   int n,m;
   dp[0]=1;
   while(scanf("%d %d",&n,&m),n|m){
     int i,j,k;
     for(i=1;i<=n;i++)
        scanf("%d",&val[i]);
     for(i=1;i<=n;i++)
        scanf("%d",&num[i]);
     for(i=1;i<=m;i++) dp[i]=0;

     for(i=1;i<=n;i++){
        for(j=0;j<=m;j++)
            use[j]=0;
        for(j=val[i];j<=m;j++)
         if(dp[j-val[i]]&&!dp[j]&&use[j-val[i]]+1<=num[i]){
          dp[j]=1;
          use[j]=use[j-val[i]]+1;;
        }
     }
     int ans=0;
     for(i=1;i<=m;i++)
        if(dp[i])
         ans++;
     printf("%d
",ans);
   }

}