#include<bits/stdc++.h>
#define v vector
using namespace std;
typedef long long let;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
let x,n;
cin >> x >> n;
v<let> c(n);
v<let> w(n);
v<let> t(n);
for(let i = 0;i<n;i++)cin >> c[i] >> w[i] >> t[i];
v<let> sum(x+1,0);
for(let i = 0;i<n;i++) t[i] = min(t[i],x/w[i]);
for(let i =0;i<n;i++){
for(let j =0;j<t[i];j++){
for(let l = x;l>=w[i];l--){
sum[l] = max(sum[l], sum[l-w[i]]+c[i]);
}
}
}
let out = 0;
for(let i = 0;i<=x;i++){
out = max(out, sum[i]);
}
cout << out;
cout << "\n";
return 0;
}
