1 #include<iostream>

 2 #include<memory.h>

 3 

using 

namespace std;

 4 

#define max(a,b) a>b?a:b

 5 

struct goods{

 6     

int v;  

//

价格

 7     

int p;  

//

重要程度

 8     

int w;  

//

v * p

 9 }a[

26];

10 

11 

int dp[

30001];

12 

13 

int main()

14 {

15 

//

    freopen("in.txt","r",stdin);

16     

int t,i,j,N,m;

17     cin>>t;

18     

while(t--)

19     {

20         memset(dp,

0,

sizeof(dp));

21         cin>>N>>m;

22         

for(i = 

0; i !=m; ++i)

23         {

24             cin>>a[i].v>>a[i].p;

25             a[i].w = a[i].v * a[i].p;

26             

for(j = N; j >= a[i].v; --j)

27                 dp[j] = max(dp[j], dp[j - a[i].v] + a[i].w);

28         }

29         cout<<dp[N]<<endl;    

30     }

31     

return 

0;

32 }