#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, s;
vector<pii> arr;
int ima[100100];
ll dp[100100][2100];
int main(){
cin>>s>>n;
for(int i = 0; i < n; i++){
int a, b;
cin>>a>>b>>ima[i];
arr.pb(mp(a,b));
}
memset(dp, 0, sizeof dp);
for(int j = 1; j * arr[0].second <= s && j <= ima[0]; j++){
dp[0][j*arr[0].second] = j * arr[0].first;
}
for(int i = 1; i < n; i++){
for(int used = 0; used <= s; used++){
dp[i][used] = max(dp[i][used], dp[i-1][used]);
for(int j = 1; j * arr[i].second + used <= s && j <= ima[i]; j++){
dp[i][j*arr[i].second + used] = max(dp[i][j*arr[i].second+used], dp[i-1][used] + arr[i].first * j);
}
}
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j <= s; j++){
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
ll best = 0;
for(int i = 0; i <= s; i++)
best = max(best, dp[n-1][i]);
cout<<best<<endl;
return 0;
}
