/* Author: Serpentx
Noob here xD */
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define vi vector<int>
#define vvi vector <vi>
#define NO { cout << "NO" << endl; return; }
#define YES {cout << "YES" << endl; return; }
#define print(v) for(auto &it:v) cout << it << ' '
const int MOD = 1e9+7;
const int INF = LLONG_MAX >> 1;
void solve() {
int S, n ;
cin >> S >> n;
vi arr, brr, crr;
for(int i=0;i<n;i++){
int a , b , c;
cin >> a >> b >> c;
for(int j=0;j<c;j++){
arr.push_back(a);
brr.push_back(b);
crr.push_back(c);
}
}
if(n==1){
int quantitiy = S / brr[0];
cout << min(quantitiy, crr[0]) * arr[0] << endl;
return;
}
n = arr.size();
vvi dp(n,vi(S+1,0));
// dp[i][j] = maximum profit using i , weight using j
dp[0][0]=0;
for(int j=brr[0];j<=S;j++){
dp[0][j]=arr[0];
}
for(int i=1;i<n;i++){
for(int j=0;j<=S;j++){
int value = arr[i];
int weight = brr[i];
if(j-weight>=0){
dp[i][j] = max(dp[i][j], max(value+dp[i-1][j-weight],dp[i-1][j]));
}
else{
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
}
}
cout << dp[n-1][S] << endl;
return;
}
signed main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
