hdu 2079

#include "stdio.h"
#include "string.h"
int c1[41];
int c2[41];

int main(){
      int i,n,m,a,j,k,T,b,t;
      int num[41];
      scanf("%d",&T);
      while(T--){
           scanf("%d%d",&n,&k);
           for(i=1;i<=k;i++){
                 scanf("%d%d",&a,&b);
                 num[a]=b;
           }
            memset(c1,0,sizeof(c1));
            memset(c2,0,sizeof(c2));
            c1[0]=1;
            for(i=1;i<=k;i++){
                 for(j=0;j<=n;j++){
                     for(t=0;t<=num[i] && t*i+j<=n;t++){
                         c2[t*i+j]+=c1[j];
                         }
                  }
                  for(j=0;j<=n;j++){
                       c1[j]=c2[j];
                       c2[j]=0;
                   }
              }
              printf("%d\n",c1[n]);
          }
         return 0;
}