#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace std;

const int MAX=;

int dp[MAX];

int c[MAX],w[MAX];

int v;

void ZeroOnePack(int cost,int wei)//

{

    int i;

    for(i = v;i>=cost;i--)

    {

        dp[i] = max(dp[i],dp[i-cost]+wei);

    }

}

void CompletePack(int cost,int wei)//完全

{

    int i;

    for(i = cost;i<=v;i++)

    {

        dp[i] = max(dp[i],dp[i-cost]+wei);

    }

}

void MultiplePack(int cost,int wei,int cnt)//多重

{

    if(v<=cnt*cost)//如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包

    {

        CompletePack(cost,wei);

        return ;

    }

    else//否则就将多重背包转化为01背包

    {

        int k = ;

        while(k<=cnt)

        {

            ZeroOnePack(k*cost,k*wei);

            cnt = cnt-k;

            k = *k;

        }

        ZeroOnePack(cnt*cost,cnt*wei);

    }

}

int main()

{

    int n;

    while(~scanf("%d%d",&n,&v),n+v)

    {

        int i;

        for(i = ;i<n;i++)

        scanf("%d",&c[i]);

        for(i = ;i<n;i++)

        scanf("%d",&w[i]);

        memset(dp,,sizeof(dp));

        for(i = ;i<n;i++)

        {

            MultiplePack(c[i],c[i],w[i]);

        }

        int sum = ;

        for(i = ;i<=v;i++)

        {

            if(dp[i]==i)

            {

                sum++;

            }

        }

        printf("%d\n",sum);

    }

    return ;

}

#include<iostream>

#include<stdio.h>

#include<algorithm>

#include<cstring>

#include<string.h>

#include<string>

using namespace std;  

int c[],w[],num[];

int dp[];

int v,V,V1;  

void ZeroOnePack(int c, int w)

{

    for(int v = V; v >=c; v--)

    {

        dp[v] = max(dp[v],dp[v-c]+w);

    }

}  

void CompletePack(int c, int w)

{

    for(int v = c; v <= V; v++)

    {

        dp[v] = max(dp[v],dp[v-c]+w);

    }

}  

void MultiplePack(int c, int w, int num)

{

    if(c * num >= V)

    {

        CompletePack(c,w);

    }

    else

    {

        int k = ;

        while(k < num)

        {

            ZeroOnePack(k*c, k*w);

            num -= k;

            k <<= ;

        }

        ZeroOnePack(num*c, num*w);

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    int n;

    int i;

    while(t--)

    {

        scanf("%d%d",&V,&n);

        for(i = ; i <=n; i++)

        {

            scanf("%d%d%d",&c[i], &w[i], &num[i]);

        }

        memset(dp,,sizeof(dp));

        for(i = ; i <= n; i++)

        {

            MultiplePack(c[i],w[i],num[i]);

        }

        printf("%d\n",dp[V]);

    }

    return ;

}