#include <bits/stdc++.h>
using namespace std;
struct termek{
int ertek;
int suly;
int mennyiseg;
};
int s, n;
vector<vector<int>> dp;
vector<termek> termekek;
int megold(int ind, int maradt){
if(maradt < 0){
return 0;
}
if(ind == n){
return 0;
}
if(dp[ind][maradt] != -1){
return dp[ind][maradt];
}
int vissza = 0;
for(int i = 0; i <= termekek[ind].mennyiseg && maradt - termekek[ind].suly * i >= 0; i++){
int a = megold(ind + 1, maradt - termekek[ind].suly * i) + termekek[ind].ertek * i;
//cout << ind << " : " << i << " : " << a << "\n";
vissza = max(vissza, a);
}
return dp[ind][maradt] = vissza;
}
int main()
{
cin >> s >> n;
dp.assign(n, vector<int>(s + 1, -1));
termekek.assign(n, {0, 0, 0});
for(int i = 0; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
termekek[i] = {a, b, c};
}
cout << megold(0, s) << "\n";
}
