求调

#include<bits/stdc++.h>
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,outd[N];
inline void add(int a,int b,int ww,int vv){
	to[++edge_num] = b;
	nex[edge_num] = head[a];
	head[a] = edge_num;
	outd[a]++;
	v[b] = vv;
	w[b] = ww;
}
inline void dfs(int now){
//	cout << now << endl;
	if(w[now]<=V){
		if(!outd[now] || w[now]==V){
			for(int i=w[now];i<=V;++i){
				ans[now][i] = v[now];
			}
		}
		else{
			for(int k=head[now];k;k=nex[k]){
				int tto = to[k];
				dfs(tto);
				for(int i=V-w[now];i>=0;--i){
					for(int j=0;j<=i;++j){
						if(ans[now][i]<ans[now][i-j]+ans[tto][j]) ans[now][i]=ans[now][i-j]+ans[tto][j];
					}
				}
			}
			for(int i=V;i>=w[now];--i) ans[now][i]=ans[now][i-w[i]]+v[now];
			for(int i=0;i<w[now];++i) ans[now][i]=0;		
		}
	}
}
int main(){
	read(V,n);
	for(int i=1,ww,vv,q;i<=n;++i){
		read(ww,vv,q);
		add(q,i,ww,ww*vv);
	}
	dfs(0);
	printf("%d",ans[0][V]);
	return 0;
}