#include<iostream>
using namespace std;
struct main_and_sub{
	int ap,ai;
}kb[114514];
int n,sum,m,dp[114514];
int main(){
	cin>>n>>m;
	n/=10;
	for(int i=1;i<=m;i++){
		int tp,ti,tm;
		cin>>tp>>ti>>tm;
		tp/=10;
		if(tm==0) kb[i].ap+=tp,kb[i].ai+=ti;
		else kb[tm].ap+=tp,kb[tm].ai+=ti;
	}
	for(int i=1;i<=m;i++){
		for(int j=n;j>=kb[i].ap;j--){
			dp[j]=max(dp[j],dp[j-kb[i].ap]+kb[i].ap*kb[i].ai);
		}
	}
	cout<<dp[n]*10;
	return 0;
}

思路就是把主件和副件整一起当一个算