yuangq @ 2018-10-03 11:22:00
#include<iostream>
#include<vector>
#include<cstring>
#define LL long long
#define MAXN 65
#define MAXC 3205
using namespace std;
//int a[MAXN];
int C,N;
struct Node
{
int v,p;
Node(int v=0,int p=0):v(v),p(p){}
} nList[MAXN];
vector<Node> Adj[MAXN];
LL dp[MAXC];
LL temp[4][MAXC];
int main()
{
//freopen("train.in","r",stdin);
//freopen("train.out","w",stdout);
cin>>C>>N;
int v,p,q;
for(int i=1;i<=N;i++)
{
cin>>v>>p>>q;
v/=10;
if(q==0)
{
nList[i]=Node(v,p);
}
else
{
Adj[q].push_back(Node(v,p));
}
}
for(int i=1;i<=N;i++)
{
if(nList[i].p==0)
{
continue;
}
memset(temp,0,sizeof(temp));
int v0=nList[i].v;
int p0=nList[i].p;
for(int j=C;j>=1;j--)
{
if(j-v0>=0)
{
temp[0][j]=max(temp[0][j],dp[j-v0]+v0*p0);
}
}
if(Adj[i].size()>0)
{
int v1=Adj[i][0].v;
int p1=Adj[i][0].p;
for(int j=C;j>=1;j--)
{
if(j-v0-v1>=0)
{
temp[1][j]=max(temp[1][j],dp[j-v0-v1]+v0*p0+v1*p1);
}
}
if(Adj[i].size()>1)
{
int v2=Adj[i][1].v;
int p2=Adj[i][1].p;
for(int j=C;j>=1;j--)
{
if(j-v0-v2>=0)
{
temp[2][j]=max(temp[2][j],dp[j-v0-v2]+v0*p0+v2*p2);
}
}
for(int j=C;j>=1;j--)
{
if(j-v0-v1-v2>=0)
{
temp[3][j]=max(temp[3][j],dp[j-v0-v1-v2]+v0*p0+v1*p1+v2*p2);
}
}
}
}
}
LL ans=0;
for(int j=1;j<=C;j++)
{
ans=max(ans,dp[j]);
}
cout<<ans*10;
return 0;
}