#include "bits/stdc++.h"
#include <utility>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) ((int)v.size())
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pry puts("YES")
#define prn puts("NO")
#define endl '\n'
#define pb push_back
#define pr first
#define wh second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n, s;
cin >> s >> n;
// worth, weight
vector<pair<ll, ll>> objs;
rep(i, n){
int a, b, c;
cin >> a >> b >> c;
c = min(c, s);
for (int pow = 1; pow < c; pow *= 2)
objs.pb(make_pair(pow * a, pow * b));
objs.pb(make_pair(c * a, c * b));
}
/*
* Iterate over all possible items in a 2 dimensional dp array
*/
vector<vector<ll>> dp(sz(objs) + 1);
for (auto &x : dp)
x.assign(s + 1, 0);
for (int i = 0; i < sz(objs); i++){
for (int j = 0; j < s+1; j++){
dp[i + 1][j] = dp[i][j];
if (j - objs[i].wh >= 0)
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - objs[i].wh] + objs[i].pr);
}
}
cout << dp[sz(objs)][s] << endl;
}
int32_t main() {
cin.tie(0); ios_base::sync_with_stdio(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
