#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
ll n, s;
vector < pair < ll, pair < ll, ll >>> a ( N );
// untung, berat, stok
void solve1 (){
// O(1)
ll ans = min ( s / a[1].second.first, a[1].second.second);
ans *= a[1].first;
cout << ans << endl;
exit(0);
}
void solve2 (){
vector < vector < ll >> dp ( 105, vector < ll > ( s + 5, 0));
// O ( N * S )
for ( int i = 1; i <= n; i++){
for ( int j = 0; j <= s; j++){
dp[i][j] = dp[i-1][j];
if ( j >= a[i].second.first ){
dp[i][j] = max ( dp[i][j], dp[i - 1][ j - a[i].second.first] + a[i].first);
}
}
}
cout << dp[n][s] << endl;
exit(0);
}
void solve(){
// O ( N * S * ( k )) -> 2e7
vector < vector < ll >> dp ( 105, vector < ll > ( s + 5, 0));
for ( int i = 1; i <= n; i++){
for ( int j = 0; j <= s; j++){
dp[i][j] = dp[i-1][j];
for ( int k = 1; k <= a[i].second.second; k++){
if ( j >= k * a[i].second.first ){
dp[i][j] = max ( dp[i][j], dp[i - 1][j - ( k * a[i].second.first)] + ( k * a[i].first));
}
}
}
}
cout << dp[n][s] << endl;
exit(0);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> s >> n;
bool y = true;
for ( int i = 1; i <= n; i++){
cin >> a[i].first >> a[i].second.first >> a[i].second.second;
if ( a[i].second.second >= 2 ) y = false;
}
// subsoal 1
if ( n == 1 ){
solve1();
}
// subsoal 2
else if ( y && n <= 100 ){
solve2();
}
// subsoal 3
else{
solve();
}
}
