/*
o((>ω< ))o
o(≧口≦)o
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define int ll
#define F first
#define S second
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
//#define endl "\n"
struct mrbeast{
int v; int w; int k;
};
struct roblox{
int w; int v;
};
void solve(){
int S,n,m;
cin >> S >> n;
vector<mrbeast> a_(1e5+10);
vector<roblox> a(3000);
vector<vector<int>> dp(3000,vector<int>(2005));
for (int i = 1; i <= n; i++) cin >> a_[i].v >> a_[i].w >> a_[i].k;
m = 0;
for (int i = 1; i <= n; i++){
for (int j = 0; (1 << j) <= a_[i].k; j++){
a[++m].w = a_[i].w*(1<<j);
a[m].v = a_[i].v*(1<<j);
}
}
// cout << endl;
// for (int i = 1; i <= m; i++) cout << a[i].w << ' ' << a[i].v << endl;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= S; j++){
dp[i][j] = dp[i-1][j];
if (a[i].w < j){
dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i].w]+a[i].v);
}
}
}
cout << dp[n][S] << endl;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int t; cin >> t; while (t--)
solve();
}
