蒟蒻T了6 7 8 9 《求调

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
	int w=0;x=0;
	char ch = getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t);read(args...);
}
const int N = 4e4;
int V,n;
int ans[70][N];
int to[N],nex[N],w[N],v[N];
int head[N],edge_num;
inline void add(int a,int b,int ww,int vv){
	
}
int vis[N];
inline void dfs(int now){
//	cout << now << endl;
	vis[now] = 1;
	for(int i=head[now];i!=-1;i=nex[i]){
		int tto = to[i];
		if(vis[tto]) continue;
		vis[tto] = 1;
		dfs(tto);
		for(int j=V-w[now];j>=0;--j){
			for(int k=0;k<=j;++k){
				if(ans[now][j]<ans[now][j-k]+ans[tto][k]) ans[now][j]=ans[now][j-k]+ans[tto][k];
			}
		}
	}
	for(int i=V;i>=0;--i){
		if(i<w[now]) ans[now][i] = 0;
		else ans[now][i] = ans[now][i-w[now]]+v[now];
	}
}
int main(){
	read(V,n);
	memset(head,-1,sizeof(head));
	for(int i=1,vv,q;i<=n;++i){
		read(w[i],vv,q);
		to[++edge_num] = i;
		nex[edge_num] = head[q];
		head[q] = edge_num;
		v[i] = vv*w[i]/10;
	}
	dfs(0);
	printf("%d",ans[0][V]*10);
	return 0;
}