1 //01背包
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 int d[30005],val;
 6 
 7 void bag(int v,int w)
 8 {
 9     for(int i=val; i>=v; --i)
10         if(d[i] < d[i-v] + w)
11             d[i] = d[i-v] + w;
12 }
13 
14 int main()
15 {
16     int t,num,v,w;
17     scanf("%d",&t);
18     while(t--)
19     {
20         memset(d,0,sizeof d);
21         scanf("%d%d",&val,&num);
22         while(num--)
23         {
24             scanf("%d%d",&v,&w);
25             bag(v,w*v);
26         }
27         printf("%d\n",d[val]);
28     }
29     return 0;
30 }