#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;
typedef pair<int, int> pii;
typedef pair<ll, int> pill;
#define fi first
#define se second
const int N = 100005;
int s, n;
int v[N], w[N], k[N];
vector <pair<ll,ll>> doVat;
int power2[20];
ll dp[2][2005];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
power2[0] = 1;
for(int i=1;i<=15;i++){
power2[i] = power2[i-1] * 2;
}
cin >> s >> n;
for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> k[i];
for(int i=1;i<=n;i++){
int soDo = k[i];
for(int j=0;j<=15;j++){
if(soDo - power2[j] < 0) break;
doVat.push_back({power2[j] * v[i], power2[j] * w[i]});
soDo -= power2[j];
}
if(soDo > 0){
doVat.push_back({soDo * v[i], soDo * w[i]});
}
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for(int i=0;i<(int)doVat.size();i++){
for(int j=0;j<=s;j++) dp[(i+1)%2][j] = -1;
for(int j=0;j<=s;j++){
if(dp[i%2][j] == -1) continue;
ll V = doVat[i].fi;
ll W = doVat[i].se;
dp[(i+1)%2][j] = max(dp[(i+1)%2][j], dp[i%2][j]);
if(j + W <= s) dp[(i+1)%2][j + W] = max(1LL*dp[(i+1)%2][j + W], 1LL*dp[i%2][j] + V);
}
}
ll ans = 0;
for(int j=0;j<=s;j++) ans = max(ans, (ll)dp[(int)doVat.size()%2][j]);
cout << ans;
return 0;
}
/*
*/
