DP大作战—组合背包

题目描述

组合背包：有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。

DD大牛的伪代码
for i = 1 to N
    if 第i件物品属于01背包
        ZeroOnePack(F,Ci,Wi)
    else if 第i件物品属于完全背包
        CompletePack(F,Ci,Wi)
    else if 第i件物品属于多重背包
        MultiplePack(F,Ci,Wi,Ni)

输入

第一个数为数据组数n 1<=n<=10

接下来n组测试数据，每组测试数据由2部分组成。

第一行为背包容量V，物品种类数N。1<=V<=30000,1<=N<=200

接下来N行每行三个数为物品价值v，物品重量w，物品件数M。M=233表示物品无限。

1<=v,w<=200, 1<=M<=25

输出

对于每组数据，输出一行，背包能容纳的最大物品价值

输入样例

1
10 3
2 2 233
3 2 1
4 3 3

输出样例

13