rt。全WA。

#include <bits/stdc++.h>
#define int long long
#define fin(x) freopen (x,"r",stdin)
#define fout(x) freopen (x,"w",stdout)
#define rnt register int 
#define pb push_back
using namespace std;
int n,m;
vector<int> f;
struct budget{
	int v,w,q;
}; 
vector<budget> a;
vector<vector<budget> > b;
inline int read () {int s=0,w=0;char c=getchar ();while (!isdigit (c)){w|=(c=='-');c=getchar ();}while (isdigit (c)) {s=(s<<1)+(s<<3)+(c^48);c=getchar ();}return w?-s:s;}
inline void write (int x) {if (x<0) putchar ('-'),x=-x;if (x>9) write (x/10);putchar (x%10|48);}
inline void writesp (int x) {write (x),putchar (' ');}
inline void writeln (int x) {write (x),putchar ('\n');}
inline bool cmp (budget x,budget y) {return x.q<y.q;}
signed main ()
{
	fin ("budget.in");
	fout ("budget.out");
	m=read (),n=read ();
	a.resize (n+1),b.resize (n+1),f.resize (m+1);
	for (rnt i=1;i<=n;++i) a[i].v=read (),a[i].w=read (),a[i].q=read ();
	for (rnt i=1;i<=n;++i) b[i].clear ();
	for (rnt i=1;i<=n;++i)
		if (a[i].q==0) b[i].pb (a[i]);
			else b[a[i].q].pb (a[i]);
//	for (rnt i=1;i<=n;++i)
//	{
//		for (int j=0;j<b[i].size ();++j)
//			writesp (b[i][j].v),writesp (b[i][j].w),writeln (b[i][j].q);
//		putchar ('\n');
//		putchar ('\n');
//	}
	for (rnt i=1;i<=n;++i)
	{
		vector<budget> s;
		if (b[i].size ()==0) continue;
		if (b[i].size ()==1) s.pb (b[i][0]),s.pb ({0,0,0});
		if (b[i].size ()==2) s.pb (b[i][0]),s.pb ({b[i][0].v+b[i][1].v,b[i][0].w+b[i][1].w,b[i][0].q}),s.pb ({0,0,0});
		if (b[i].size ()==3) s.pb ({0,0,0}),s.pb (b[i][0]),s.pb ({b[i][0].v+b[i][1].v,b[i][0].w+b[i][1].w,b[i][0].q}),s.pb ({b[i][0].v+b[i][2].v,b[i][0].w+b[i][2].w,b[i][0].q}),s.pb ({b[i][0].v+b[i][1].v+b[i][2].v,b[i][0].w+b[i][1].w+b[i][2].w,b[i][0].q});
		for (rnt k=m;k>0;--k)
			for (rnt j=0;j<s.size ();++j)
				if (k>=s[j].v)
					f[k]=max (f[k],f[k-s[j].v]+s[j].w*s[j].v);
	}
	write (f[m]);
	return 0;
}