// #pragma GCC optimize("Ofast,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#ifdef LOCAL
#define debug(val) cerr << "["#val << " = " << (val) << "] "
#define slash() cerr << "\n-----------\n"
#define time() cerr << "Time is: " << 1000 * clock()/CLOCKS_PER_SEC << " ms\n"
#else
#define debug(val) 1407
#define slash() 1407
#define time() 1407
#endif
const string filename = "";
int n, W;
vector<pair<int, int>> v;
void solve(){
cin >> W >> n;
int bits = 1;
for(int i=0;i<n;i++){
int a, b, c; cin >> b >> a >> c;
// c = min(c, 2 * W);
bits = 1;
while(c - bits >= 0){
if(1ll * a * bits <= W) {
v.push_back({a * bits, b * bits});
}
c -= bits;
bits *= 2;
}
if(c){
if(1ll * c * a <= W) {
v.push_back({c * a, c * b});
}
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
vector<int> dp(W+1, 0);
for(int i=0;i< (int)v.size();i++){
for(int j=W;j >= v[i].first;j--){
dp[j] = max(dp[j], dp[j-v[i].first] + v[i].second);
}
}
cout << dp[W];
}
signed main(){
int test = 1;
/* cin >> test; */
for(int i=1;i<=test;i++){
// cout << "Case " << "#" << i << ": ";
solve();
}
return 0;
}
