#include <bits/stdc++.h> using namespace std; int s,n; int w[100005]; long long v[100005],k[100005],dp[2005]; priority_queue<pair<long long,long long>> q[2005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>s>>n; for(int i=0;i<n;i++) { cin>>v[i]>>w[i]>>k[i]; q[w[i]].push({v[i],k[i]}); } for(int x=1;x<=s;x++) { long long c=s/x; while(!q[x].empty() && c>0) { pair<long long,long long> p=q[x].top(); q[x].pop(); long long t=p.second; if(t>c) { t=c; } c-=t; for(int y=0;y<t;y++) { for(int z=s;z>=x;z--) { dp[z]=max(dp[z],dp[z-x]+p.first); } } } } long long a=0; for(int i=1;i<=s;i++) { a=max(a,dp[i]); } cout<<a; return 0; }