#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int,int>> Vec[2005];
int dp[2005];
int main(){
int S, n, Ans = 0;
cin>>S>>n;
for (int i=1, v, w, k;i<=n;i++){
cin>>v>>w>>k;
Vec[w].push_back({v, k});
}
for (int i=1;i<=S;i++)
dp[i] = -2e9;
for (int i=1;i<=S;i++){
int MaxI = S / i;
sort(begin(Vec[i]), end(Vec[i]));
while (MaxI > 0 and Vec[i].size() > 0){
auto [v, k] = Vec[i].back();
Vec[i].pop_back();
for (int j=S;j>=i;j--)
dp[j] = max(dp[j], dp[j - i] + v);
if (k - 1)
Vec[i].push_back({v, k-1});
MaxI--;
}
Ans = max(Ans, dp[i]);
}
cout<<Ans<<'\n';
}
