#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll maxn = 2003;
const ll mod = 1e9 + 7;
struct TPair
{
ll v , k;
};
bool ss(TPair i , TPair j)
{
return i.v > j.v;
}
ll dp[maxn][maxn] , inf = 1e18;
vector<TPair>a[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("","r",stdin);
//freopen("","w",stdout);
int s , n;
cin>>s>>n;
ll v , w , k;
for(int i = 1 ; i <= n ; ++i)
{
cin>>v>>w>>k;
a[w].push_back({v , k});
}
for(int i = 1 ; i <= s ; ++i)
sort(a[i].begin() , a[i].end() , ss);
ll kq = 0;
for(int i = 1 ; i <= s ; ++i)
dp[i][0] = -inf;
for(int i = 0 ; i <= s ; ++i)
dp[0][i] = 0;
for(int j = 1 ; j <= s ; ++j)
{
for(int i = 1 ; i <= s ; ++i)
{
dp[i][j] = dp[i][j - 1];
ll so1 = 0 , so2 = 0;
for(TPair h : a[j])
{
int dem = 0;
while(dem < h.k)
{
++dem;
so1 += j;
so2 += h.v;
if(so1 > i) goto done;
dp[i][j] = max(dp[i][j] , dp[i - so1][j - 1] + so2);
}
}
done:;
kq = max(kq , dp[i][j]);
}
}
cout<<kq;
}
