View Code of Problem 850

//#include<cstdio>
//#include<algorithm>
//#include<iostream>
//#include<string.h>
//using namespace std;
//#define INF 0x3f3f3f3f
//#define maxn 100005
////多重背包
//int dp[maxn];
//int volume[105],value[105],c[105];
//int n,v;
//void ZeroOnepark(int val,int vol){
//	for(int j=v;j>=vol;j--){
//		dp[j]=max(dp[j],dp[j-vol]+val);
//	}
//}
// 
//void Completepark(int val,int vol){
//	for(int j=vol;j<=v;j++){
//		dp[j]=max(dp[j],dp[j-vol]+val);
//	}
//} 
// 
//void Multiplepark(int val,int vol,int amount){
//	if(vol*amount>=v){
//		Completepark(val,vol);
//	}
//	else{
//		int k=1;
//		while(k<amount){
//			ZeroOnepark(k*val,k*vol);
//			amount-=k;
//			k<<=1;
//		}
//		if(amount>0){
//			ZeroOnepark(amount*val,amount*vol);
//		}
//	}
//} 
// 
//int main(void){
//	while(cin>>n>>v){
//		int t=0; 
//		if(n==0&&v==0)
//			break;
//		for(int i=1;i<=n;i++){
//			cin>>volume[i];
//		}
//		for(int i=1;i<=n;i++){
//			cin>>c[i];
//		}
//		memset(dp,0,sizeof dp);
//		for(int i=1;i<=n;i++){
//			Multiplepark(volume[i],volume[i],c[i]);
//		}
//
//		for(int i=1;i<=v;i++){
////			cout<<dp[i]<<endl;
//			if(dp[i]==i)
//				t++;
//		}
//		cout<<t<<endl;
//	}	
//
//}
#include <stdio.h>
#include <string.h>
#define coin_maxn 105
#define maxn 100100

int coin[coin_maxn];
int amount[coin_maxn];
int dp[maxn];
int used[maxn];

int nCoin, nSum;

void solve()
{
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	int i,j;
	for(i = 0; i < nCoin; i++)
	{
		memset(used, 0, sizeof(used));
		for( j = coin[i]; j <= nSum; j++)
		{
			if(dp[j-coin[i]] && !dp[j] && used[j-coin[i]] + 1 <= amount[i])
			{
				dp[j] = 1;
				used[j] = used[j-coin[i]] + 1;
			}
		}
	}
	int count = 0;
	for( i = 1; i <= nSum; i++)
	{
		count += dp[i];
	}
	printf("%d\n",count);
}


int main()
{
	int i,j;
	while(scanf("%d%d", &nCoin, &nSum) != EOF)
	{
		if(nCoin == 0 && nSum == 0)
		{
			break;
		}
		for(i = 0; i <  nCoin; i++)
		{
			scanf("%d", &coin[i]);
		}
		for( i = 0; i < nCoin; i++)
		{
			scanf("%d", &amount[i]);
		}
		solve();
	}
	return 0;
}