HDU2079

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define M 40
#define N 10
#define MS(x) memset(x,0,sizeof(x))
int n,m;
int num[N+1],val[N+1];
int c1[M+1],c2[M+1];
void solve()
{
    MS(c1);
    MS(c2);
    int i,j,k;
    for(i=0;i<=num[1]*val[1];i+=val[1])
        c1[i]=1;
    for(i=2;i<=n;++i)
    {
        for(j=0;j<=m;++j)
        {
            for(k=0;k+j<=m&&k<=num[i]*val[i];k+=val[i])
            {
                c2[k+j]+=c1[j];
            }
        }
        for(j=0;j<=m;++j)
        {
            c1[j]=c2[j];
            c2[j]=0;
        }
    }
}
int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        int k;
        MS(num);
        MS(val);
        scanf("%d%d",&m,&n);
        for(i=1;i<=n;++i)
        scanf("%d%d",&val[i],&num[i]);
        solve();
        printf("%d\n",c1[m]);
    }
  //  cout << "Hello world!" << endl;
    return 0;
}