1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 3000 5 using namespace std; 6  7 int dp[maxn]; 8 int a,b; 9 int t,n,k;10 11 int main()12 {13     scanf("%d",&t);14     while(t--)15     {16         scanf("%d%d",&n,&k);17         memset(dp,0,sizeof(dp));18         dp[0]=1;19         for(int i=1; i<=k; i++)20         {21             scanf("%d%d",&a,&b);22             for(int j=n; j>=a; j--)23             {24                 for(int x=1; x<=b; x++)25                 {26                     if(j-x*a>=0)27                     {28                         dp[j]+=dp[j-x*a];29                     }30                 }31             }32         }33         printf("%d\n",dp[n]);34     }35     return 0;36 }