> #include <stdio.h>
> #include <string.h>
> #define maxn 2010
> 
> int max,t,l,m,n,d,v[11][2],f[maxn];
> 
> void doit()
> {
>   int i,j,k,z,s;
> 
>   l=0; max=0; f[0]=0;
>   for (i=1; i<maxn; i++)
>   f[i]=-1;
>   for (i=1; i<=n; i++)
>   {
>     z=m/1000;
>     for (j=l/1000+1; j<=z; j++)
>     {  for (k=0; k<d; k++)
>        {
>          s=v[k][0];
>          if (j>=s && f[j-s]>=0 && f[j-s]+v[k][1]>f[j])
>            f[j]=f[j-s]+v[k][1];
>        }
>        if (f[j]>max) max=f[j];
>     }
>     l=m; m+=max;
>   }
>   printf("%d\n",m);
> }
> 
> int main()
> {
>   int i,j;
> 
>   scanf("%d",&t);
>   for (i=0; i<t; i++)
>   {
>     scanf("%d%d%d",&m,&n,&d);
>     memset(v,0,sizeof(v));
>     for (j=0; j<d; j++)
>     {  scanf("%d%d",&v[j][0],&v[j][1]);
> 	   v[j][0]/=1000;
>     }
>     doit();  
>   }
>   return 0;
> }