meiqwq @ 2017-04-28 22:26:46
#include<iostream>
#define maxx(x,y) x>y ? x:y;
using namespace std;
int n,m,v[61],c[61],q[61],q1[61],q2[61],dp[32001];
int main()
{
int i,j,k;
cin>>n>>m;
n/=10;
for(i=1;i<=m;i++)
{
cin>>v[i]>>c[i]>>q[i];
c[i]*=v[i];
v[i]/=10;
if(q[i]!=0)
{
if(q1[i]==0)q1[q[i]]=i;
else q2[q[i]]=i;
}
}
for(i=1;i<=m;i++)
{
for(j=n;j>-1;j--)
{
if(q[i]!=0)continue;
if(j-v[i]>=0)
{
dp[j]=maxx(dp[j],dp[j-v[i]]+c[i]);
if(q1[i]!=0)
{
if(j-v[i]-v[q1[i]]>=0)dp[j]=maxx(dp[j],dp[j-v[i]-v[q1[i]]]+c[i]+c[q1[i]]);
if(q2[i]!=0)
{
if(j-v[i]-v[q2[i]]>=0)dp[j]=maxx(dp[j],dp[j-v[i]-v[q2[i]]]+c[i]+c[q2[i]]);
if(j-v[i]-v[q1[i]]-v[q2[i]]>=0)dp[j]=maxx(dp[j],dp[j-v[i]-v[q1[i]]-v[q2[i]]]+c[i]+c[q1[i]]+c[q2[i]]);
}
}
}
}
}
cout<<dp[n];
}