#include <bits/stdc++.h>
using namespace std;
int main() {
long long int s , n;
cin >> s >> n;
if (n==1){
int a , b , c;
cin >> a >> b >> c;
if (b <= s){
int sh = 0;
while (b <= s){
sh++;
s -= b;
}
cout << min(sh , c) * a;
}
else {
cout << 0;
}
return 0;
}
vector <pair<long long int,long long int>> ka;
for (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 (int i = 0 ; i < dp.size() ; i++){
dp3[i] = dp[i];
}
for (int i = 0 ; i < dp.size() ; i++){
dp[i] = dp2[i];
}
for (int i = 0 ; i < dp.size() ; i++){
dp2[i] = dp3[i];
}
dp3.clear();
}
long long int ans = 0;
for (long long int j = 0 ; j <= s ; j++){
ans = max(ans , dp[j]);
}
cout << ans << endl;
return 0;
}
