#include <bits/stdc++.h>
using namespace std;
int main() {
long long int s , n;
cin >> s >> n;
vector <pair<long long int,long long int>> ka;
for (long long int i = 0 ; i < n ; i++){
long long int a , b , c;
cin >> a >> b >> c;
for (long long int j = 0 ; j < c ; j++) {
ka.push_back(make_pair(b , a));
}
}
vector <long long int> dp(s+1 , 0);
vector <long long int> dp3(s+1 , 0);
for (auto it : ka){
long long int w = it.first;
long long int v = it.second;
vector<long long int> dp2 = dp;
for (long long int j = 0 ; j+w <= s ; j++){
dp2[j+w] = max(dp2[j+w] , dp[j]+v);
}
for (long long int i = 0 ; i < dp.size() ; i++){
dp3[i] = dp[i];
}
for (long long int i = 0 ; i < dp.size() ; i++){
dp[i] = dp2[i];
}
for (long long int i = 0 ; i < dp.size() ; i++){
dp2[i] = dp3[i];
}
dp3.clear();
}
long long int ans = 0;
for (long long int i = 0 ; i <= s ; i++){
ans = max(ans , dp[i]);
}
cout << ans;
return 0;
}
