#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
tree_order_statistics_node_update>;
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()
void solve(){
int s,n; cin >> s >> n;
vector<ll> dp(s+1,0);
while(n--){
int v,w,k; cin >> v >> w >> k;
k = min(k,s/w);
int cur = 1;
while(true){
k-=cur;
for(int i = s; i >= cur*w; i--)
dp[i] = max(dp[i],dp[i-cur*w] + 1ll*cur*v);
cur <<= 1;
if(k < cur) break;
}
if(k){
for(int i = s; i >= k*w; i--)
dp[i] = max(dp[i],dp[i-k*w] + 1ll*k*v);
}
for(int i = 1; i <= s; i++) dp[i] = max(dp[i],dp[i-1]);
}
cout << *max_element(all(dp));
}
signed main(){
// freopen("snowcow.in","r",stdin);
// freopen("snowcow.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
int t = 1;
while(t--) solve();
}
