#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
bool ckmin(long long& a, long long b){ return b < a ? a = b, true : false; }
bool ckmax(long long& a, long long b){ return b > a ? a = b, true : false; }
const int MAXS = 2000;
int s, n;
long long dp[MAXS + 1];
vector<pair<long long, int>> v[MAXS + 1];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> s >> n;
for(int i = 0; i < n; i++){
long long value;
int weight, cnt;
cin >> value >> weight >> cnt;
if(weight <= s && cnt > 0){
v[weight].push_back(make_pair(value, cnt));
}
}
for(int weight = 1; weight <= s; weight++){
sort(v[weight].begin(), v[weight].end(), [](pair<long long, int> &p1, pair<long long, int> &p2){
return p1.first > p2.first;
});
vector<long long> sums;
long long curr = 0;
int copies = 0, at = 0, used = 0;
for(int j = s; j >= 0; j--){
if(at < sz(v[weight]) && j + (copies + 1) * weight <= s){
curr += v[weight][at].first;
sums.push_back(curr);
copies++;
used++;
if(used == v[weight][at].second){
used = 0;
at++;
}
}
for(int k = 0; k < copies; k++){
ckmax(dp[j + (k + 1) * weight], dp[j] + sums[k]);
}
}
// cout << weight << '\n';
// for(auto x : sums) cout << x << ' ';
// cout << '\n' << '\n';
}
// for(int i = 0; i <= s; i++) cout << dp[i] << ' ';
cout << *max_element(dp, dp + s + 1);
return 0;
}
