#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[2][2100];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
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%2][used] = 0;
for(int used = 0; used <= s; used++){
dp[i%2][used] = max(dp[i%2][used], dp[(i-1)%2][used]);
for(int j = 1; j * arr[i].second + used <= s && j <= ima[i]; j++){
dp[i%2][j*arr[i].second + used] = max(dp[i%2][j*arr[i].second+used], dp[(i-1)%2][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)%2][i]);
cout<<best<<endl;
return 0;
}
