#include<iostream>
#define MAX 61
using namespace std;
int N,m,x;
struct thing
{
int v,p,q;
};
thing T[MAX];
bool zf[MAX];
void input()
{
int i;
freopen("budget.in","r",stdin);
freopen("budget.out","w",stdout);
cin>>N>>m;
for(int j=0;j<m+1;j++)zf[j]=0;
for(i=1;i<=m;i++)
{
cin>>T[i].v>>T[i].p>>T[i].q;
if(T[i].q==0)
{
zf[x]=1;
x++;
}
}
}
int budget(thing T[],int i,int left,int tv)
{
if(i==N)
{
if(T[N].v<left)return tv+=T[N].v*T[N].p;
else return tv;
}
if(T[i].q!=0)
{
for(int h=1;h<=x;h++)
{
if(zf[T[i].q]==1)
{
if(budget(T,i+1,left-=T[i].v,tv+=T[i].v*T[i].p)>budget(T,i+1,left,tv))return budget(T,i+1,left-=T[i].v,tv+=T[i].v*T[i].p);
else return budget(T,i+1,left,tv);
}
}
return budget(T,i+1,left,tv);
}
if(budget(T,i+1,left-=T[i].v,tv+=T[i].v*T[i].p)>budget(T,i+1,left,tv))return budget(T,i+1,left-=T[i].v,tv+=T[i].v*T[i].p);
else return budget(T,i+1,left,tv);
}
int main()
{
input();
cout<<budget(T,1,N,0);
system("pause");
return 0;
}
我是新手,哪里出错的请各位大牛告诉我