#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define mp make_pair
#define sz(a) a.size()
#define MOD 1000000007
#define forn(i, n) for (int i = 0; i < n; ++i)
#define INF 1e18
const vector<pair<int, int>> dirs1 = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, 0}, {1, 0}, {0, 1}, {0, -1}};
const vector<pair<int, int>> dirs2 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
bool sortbysec(const pair<int, int> &a, const pair<int, int> &b) { return (a.second < b.second); }
const int maxN = 100001;
int dp[maxN][2001];
vi v,w,k;
void solve(){
int n,s;
cin>>s>>n;
forn(i,n){
int x,y,z;
cin>>x>>y>>z;
v.pb(x), w.pb(y), k.pb(z);
}
dp[0][0] = 0;
for(int i=1;i<=n;++i){
for(int j=1;j<=s;++j){
dp[i][j] = dp[i-1][j];
for(int t=1;t<=k[i-1];++t){
if(j >= t*w[i-1])dp[i][j] = max(dp[i][j], dp[i-1][j-t*w[i-1]] + v[i-1]*t);
else break;
}
}
}
cout<<dp[n][s]<<"\n";
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
