#include<bits/stdc++.h> using namespace std; int m,n,t,x,g[101][1001],b[101],c[1001],w[1001],dp[1001]; int main() { cin>>m>>n; for(int i=1;i<=n;i++) cin>>c[i]>>w[i]>>x,t=max(t,x),g[x][++b[x]]=i; for(int i=1;i<=t;i++) for(int j=m;j>=0;j--) for(int k=1;k<=b[i];k++) if(j>=c[g[i][k]]) dp[j]=max(dp[j],dp[j-c[g[i][k]]]+w[g[i][k]]); cout<<dp[m]; }