hdu 1963 Investment 多重背包

//多重背包
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 1000000 + 10;
#define N 15
long long dp[maxn], ans;
int c[N], w[N], V;
void Pack(int C, int W)
{
    for(int i = C; i < maxn; i++)
        dp[i] = max(dp[i], dp[i-C]+W);
}
int main()
{
    int n, d, y;
    scanf("%d", &n);
    while(n--){
        scanf("%d%d", &V, &y);
        scanf("%d", &d);
        for(int i = 1; i <= d; i++){
            scanf("%d%d", &c[i], &w[i]);
            c[i] /= 1000;
        }
        memset(dp, 0, sizeof(dp));
        ans = V;
        V /= 1000;
        for(int i = 1; i <= d; i++)
            Pack(c[i], w[i]);
        while(y--)
            ans += dp[ans/1000];
        cout << ans << endl;    
    }
    return 0;
}