#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define file(Name) freopen(Name".inp", "r", stdin); freopen(Name".out", "w", stdout);
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)
using namespace std;
const int Maxn = 2e3+5;
const int mod = 1e9+7;
const int inf32 = 2e9+5;
const long long inf64 = 2e18+7;
int s, n;
vector<pair<int, int>> g[Maxn];
ll f[Maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//freopen("test.inp", "r", stdin); freopen("hoc.out", "w", stdout);
cin >> s >> n;
f1(i,1,n)
{
int v, w, k; cin >> v >> w >> k;
g[w].push_back({v,k});
}
f1(w,1,2e3)
{
if (!g[w].size()) continue;
sort(g[w].begin(), g[w].end(), greater<pair<int, int>>());
rf(i,s,1)
{
int cnt = 0, pos = 0, cnt_use = 0;
ll val = 0;
while((cnt+1)*w <= i && pos < g[w].size())
{
cnt++;
val += g[w][pos].fi;
f[i] = max(f[i], f[i-cnt*w] + val);
cnt_use++;
if (cnt_use == g[w][pos].se) cnt_use = 0, pos++;
}
}
}
cout << f[s];
return 0;
}
