#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define int long long
const int N = 1e6 +7;
const int inf = 1e18;
const int mod = 1e9 + 7;
/*int binpow(int a,int b){
a %= mod;
int res = 1;
while(b > 0){
if(b % 2 == 1){
res = res * a % mod;
}
a = a * a % mod;
b /= 2;
}
return res;
} */
int dp[N];
void solve(){
int s,n;
cin >> s >> n;
vector<pair<int,int>>a;
for(int i = 0;i < n; i ++){
int v,w,k;
cin >>v >>w >> k;
for(int j = 0; j < k; j ++){
a.pb({v,w});
}
}
for(int i = 0; i < a.size(); i ++){
for(int j = s; j >= a[i].second; j --){
dp[j] = max(dp[j],dp[j - a[i].second] + a[i].first);
}
}
int mx = 0;
for(int i = 0; i <= s; i ++){
mx = max(dp[i],mx);
}
cout << mx << "\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t --){
solve();
}
}
