#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxs = 2001;
int main() {
int s, n;
cin >> s >> n;
vector<pair<pair<ll, int>, int>> item(n);
for(int i = 0 ; i < n ; i++){
cin >> item[i].first.first >> item[i].first.second >> item[i].second;
//. >> value >> weight >> number
}
//1. We can safely assume WK < S, and thus we decrease K_i (note that s < 2000, actually!)
for(int i = 0 ; i < n ; i++){
item[i].second = min(item[i].second, s / item[i].first.second);
}
vector<int> dp(mxs);
for(int i = 0 ; i < n ; i++){
for(int pos = mxs - 1 ; pos > -1 ; pos--){
for(int num = 1 ; num <= item[i].second ; num++){
if(pos + num * item[i].first.second < mxs) {
dp[pos + num * item[i].first.second] = max(0LL + dp[pos + num * item[i].first.second],
0LL + dp[pos] + num * item[i].first.first);
}
}
}
}
for(int i = 0 ; i < s + 1 ; i++){
//cout << dp[i] << " ";
}//cout << endl;
cout << dp[s] << endl;
}
