#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define srt(x) sort(all(x))
#define rev(x) reverse(all(x))
#define rsrt(x) sort(rall(x))
#define sz(x) (int)x.size()
#define fi first
#define se second
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vll>;
const ll inf=1e18;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ll s, n; cin>>s>>n;
map<int, vector<pair<int, int>>> by_w;
for(int i=0; i<n; i++){
int v, w, k; cin>>v>>w>>k;
by_w[w].pb({v, k});
}
vll dp(s+1);
for(auto &[w, items] : by_w){
rsrt(items);
for(int j=s; j>=w; j--){
int c = 0, type = 0, used = 0;
ll profit = 0;
while((c+1)*w <= j && type < sz(items)){
c++;
profit += items[type].first;
dp[j] = max(dp[j], dp[j-c*w]+ profit);
used++;
if(used == items[type].second){ type++; used = 0; }
}
}
}
cout<<dp[s]<<'\n';
}
