#include<iostream>
#include<vector>
using namespace std;
int s, n;
//good: {price, weight, quantity}
int a[100001][3];
int solve() {
int dp[n+1][s+1];
for (int i=0; i<n; i++) {
for (int j=0; j<=s; j++) dp[i][j] = 0;
}
int res = 0;
for (int i=0; i<n; i++) {
int price = a[i][0], weight = a[i][1], quantity = a[i][2];
for (int j=s; j>=0; j--) {
int maxPrice = price*quantity;
int maxWeight = weight*quantity;
for (int k=quantity; k>0; k--, maxWeight-=weight, maxPrice-=price) {
if (j-maxWeight < 0 || (dp[i][j-maxWeight] == 0 && j-maxWeight != 0)) continue;
dp[i][j] = max(dp[i][j], dp[i][j-maxWeight] + maxPrice);
dp[i+1][j] = dp[i][j];
res = max(res, dp[i][j]);
}
}
}
// for (int i=0; i<n; i++) {
// for (int j=0; j<=s; j++) cout << dp[i][j] << " ";
// cout << "\n";
// }
return res;
}
int main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
cin >> s >> n;
for (int i=0; i<n; i++) {
for (int j=0; j<3; j++) {
cin >> a[i][j];
}
}
cout << solve() << "\n";
}
