#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
#define ll long long
#define ld long double
#define mod 1000000007
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
vector<pair<int,int> > arr[2001];
bool compare (pair <int, int> a, pair <int, int> b) {
return a.first > b.first;
}
int dp[2001][2001];
int solve(int i,int rem){
if(i==0 || rem==0) return 0;
if(dp[i][rem]!=-1) return dp[i][rem];
int ans = solve(i-1,rem);
int sum=0,w=0;
for (auto j : arr[i]) {
int val = j.first,k=j.second;
while (k--) {
sum += val;
w += i;
if (w > rem) {
return dp[i][rem] = ans;
}
ans = max(ans, sum + solve(i - 1, rem - w));
}
}
return dp[i][rem] = ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int s,n;
cin>>s>>n;
memset(dp,-1,sizeof dp);
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
arr[b].push_back({a,c});
}
for(int i = 1; i <= 2000; i++) {
sort(arr[i].begin(),arr[i].end(),compare);
}
cout<<solve(2000,s);
return 0;
}
