其实就是做若干次的完全背包，每做一次都更新一下钱的总数。需要注意的是，因为钱的总数可能会很大，所以需要进行缩小，以免MLE。缩小方法是，因为每一种证券的价钱都是1000的倍数，故我们可以将它们的价钱都缩小为原来的1/1000(而利息不变)。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define mst(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct bond{
int val,inte;
};
bond arr[15];
int dp[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
int begin;int year;
cin>>begin>>year;
int vtot=begin/1000;
int d;
cin>>d;
for(int i=1;i<=d;i++){
cin>>arr[i].val>>arr[i].inte;
arr[i].val/=1000;
}
int ans=begin;
for(int y=0;y<year;y++)
{
int maxi=-1;mst(dp,0);
vtot=ans/1000;
for(int i=1;i<=d;i++)
{
for(int j=arr[i].val;j<=vtot;j++)
{
int tmp=arr[i].inte;
dp[j]=max(dp[j],dp[j-arr[i].val]+tmp);
maxi=max(maxi,dp[j]);
}
}
ans+=dp[vtot];
}
cout<<ans<<endl;
}
return 0;
}