#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vt vector
#define arr array
#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
const int MOD1=998244353;
const int MOD2=1e9+7;
const ll LINF=1e18;
const int INF=1e9;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll s, n;
cin>>s>>n;
vt<arr<ll, 3>> items, use_items;
for (int i=0; i<n; i++){
ll v, w, k;
cin>>v>>w>>k;
items.pb({v, w, k});
}
sort(ALL(items), [](arr<ll, 3> l, arr<ll, 3> r){
if (l[1]==r[1]) return l[0]>r[0];
return l[1]<r[1];
});
map<ll, ll> mp;
for (int i=0; i<n; i++){
ll value=items[i][0], weight=items[i][1], total=items[i][2];
if (mp[weight] * weight > s) continue;
mp[weight]+=total;
use_items.pb({value, weight, total});
}
swap(use_items, items);
vt<ll> dp(s+1, 0);
for (int i=0; i<n; i++){
ll value=items[i][0], weight=items[i][1], total=items[i][2];
for (int j=s; j>=0; j--){
ll cnt=0;
while(cnt <= total && cnt * weight <= j){
dp[j]=max(dp[j], dp[j - cnt * weight] + value * cnt);
cnt++;
}
}
}
cout<<dp[s]<<'\n';
return 0;
}
