http://poj.org/problem?id=2063

//  ：John    ，         ，         ，(    ：      1000   )
//           ？
//    ，           。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int dp[100000];
int val[100];
int weight[100];
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int T,t,m,n;
    int sum,tem,ans;
    scanf("%d",&T);
    while(T--)
    {
        ans=tem=sum=0;
        scanf("%d%d%d",&m,&n,&t);//m       ,n    。
        for(int i=0; i<t; i++)
        {
            scanf("%d%d",&weight[i],&val[i]);
            weight[i]/=1000;
        }
        ans=m;
        for(int g=0; g<n; g++)
        {
            sum=ans/1000;
            for(int i=0; i<=sum; i++)
                 dp[i]=0;
            for(int k=0; k<t; k++)
                for(int j=weight[k]; j<=sum; j++)
                {
                    dp[j]=max(dp[j],dp[j-weight[k]]+val[k]);
                }
             ans+=dp[sum];
        }
        printf("%d
",ans);
    }
    return 0;
}