#include<iostream> using namespace std; int w[101][1001],v[101][1001],id[101]; int dp[101][1001]; int main(){ int m,n,a,b,c,cnt=0; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>a>>b>>c; id[c]++; w[c][id[c]]=a; v[c][id[c]]=b; cnt=max(cnt,c); } for(int i=1;i<=cnt;i++){ for(int j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]; for(int k=1;k<=id[i];k++){ if(j-w[i][k]>=0){ dp[i][j]=max(dp[i-1][j-w[i][k]]+v[i][k],dp[i][j]); } } } } cout<<dp[cnt][m]<<endl; return 0; }