题意：有n个商店，有m金钱，一个商店买x件商品需要x*w[i]的金钱，得到a[i] * x + b[i]件商品(x > 0)，问最多能买到多少件商品

01背包+完全背包：首先x == 1时，得到a[i] + b[i]，若再买得到的是a[i]，那么x == 1的情况用01背包思想，x > 1时就是在01的基础上的完全背包。背包dp没刷过专题，这么简单的题也做不出来:(

 

/************************************************

* Author        :Running_Time

* Created Time  :2015-8-20 12:35:33

* File Name     :E.cpp

************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int MAXN = 1e3 + 10;

const int MAXM = 2e3 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

int a[MAXN], b[MAXN], w[MAXN];

int dp[MAXM];

int main(void)    {

    //HDOJ 5410 CRB and His Birthday

   int T;  scanf ("%d", &T);

   while (T--) {

       int m, n;   scanf ("%d%d", &m, &n);

       for (int i=1; i<=n; ++i)    {

           scanf ("%d%d%d", &w[i], &a[i], &b[i]);

       }

       memset (dp, 0, sizeof (dp));

       for (int i=1; i<=n; ++i)    {

           for (int j=m; j>=w[i]; --j) {

               dp[j] = max (dp[j], dp[j-w[i]] + a[i] + b[i]);

           }

           for (int j=w[i]; j<=m; ++j) {

               dp[j] = max (dp[j], dp[j-w[i]] + a[i]);

           }

       }

       printf ("%d\n", dp[m]);

   }

   return 0;

}