#include <bits/stdc++.h>
using namespace std;
#define FOR(a, b) for(ll i = a; i < b; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long int ll;
typedef pair<ll, ll> pll; // comments that are mixed
typedef vector<ll> vll; // in with code are placed
typedef vector<pll> vpll; // on the right side
typedef vector<bool> vb;
typedef vector<char> vc;
struct item {
ll v, w, k;
};
bool cmp(item& a, item& b) {
if(a.w == b.w) return a.v < b.v;
return a.w < b.w;
}
int main() {
fast
ll s, n;
cin >> s >> n;
vll dp(s + 1, -1);
dp[0]=0;
vector<item> items(n);
FOR(0, n) cin >> items[i].v >> items[i].w >> items[i].k;
sort(items.begin(), items.end(), cmp);
ll amt=s, cur_w=1;
FOR(0, n) {
if(items[i].w < cur_w) continue;
if(items[i].w > cur_w) {
cur_w=items[i].w;
amt=s / cur_w;
}
for(ll i2=0; i2 < items[i].k; i2++) {
for(ll i3=s; i3 >= cur_w; i3--) {
if(dp[i3 - cur_w] >= 0) dp[i3] = max(dp[i3], dp[i3 - cur_w] + items[i].v) ;
}
amt--;
if(!amt) {
cur_w++;
amt=s / cur_w;
break;
}
}
}
ll ans=0;
FOR(1, s + 1) ans=max(ans, dp[i]);
cout << ans;
return 0;
}
