C :

#include <stdio.h>
#include <stdlib.h>
#define maxn 30
#define maxv 3010
#define max(A,B) ((A)<(B))?(B):(A)
typedef struct{
int price, value, q;
}Node;

Node item[maxn];
int isbuy[maxn][maxv];
int dp[maxv];
int main()
{
    int N, M;
    while(scanf("%d%d",&N, &M) != EOF) {
        for(int i = 1;i <= M; i++){
                scanf("%d%d%d",&item[i].price,&item[i].value,&item[i].q);
        }
        for(int i = 0;i <= N; i++)dp[i]=0;
        for(int i = 0;i <= M; i++){
            for(int j = 0;j <= N;j++){
                isbuy[i][j]=0;
            }
        }
        for(int i=1; i<= M; i++){
            if(item[i].q==0){
                for(int j = N;j >= item[i].price; j--){
                    if(isbuy[i][j]==0){
                     dp[j]=max(dp[j],dp[j-item[i].price]+item[i].price*item[i].value);
                     isbuy[i][j]=1;
                    }
                }
            }
            if(item[i].q!=0){
                for(int j = N;j >= item[i].price+item[item[i].q].price; j--){
                    if(isbuy[item[i].q][j]==0){
                        dp[j]=max(dp[j],dp[j-item[i].price-item[item[i].q].price]+(item[i].price+item[item[i].q].price)*(item[i].value+item[item[i].q].value));
                        isbuy[item[i].q][j]=1;
                    }
                    if(isbuy[item[i].q][j]!=0){
                        dp[j]=max(dp[j],dp[j-item[i].price]+item[i].price*item[i].value);
                    }
                }
            }
        }
        printf("%d\n",dp[N]);
    }
    return 0;
}