#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ft first
#define se second
#define NAME "A"
#define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout);
#define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define el cout << "\n"
const int MOD = 1e9 + 7, N = 1e5 + 5;
int n, S;
int32_t main(){
sdf
cin >> S >> n;
map<int, vector<pair<int, int>>> by_weight;
for(int i = 1;i <= n;++i){
int v, w, k;
cin >> v >> w >> k;
by_weight[w].push_back({v, k});
}
int in = 1, ans = 0 ;
vector<vector<int>> dp(by_weight.size() + 2, vector<int>(S+10, -1e17));
dp[0][0] = 0;
for(auto &[w, a] : by_weight){
sort(a.begin(), a.end(), greater<pair<int, int>>());
for(int j = 0;j <= S;++j){
dp[in][j] = dp[in-1][j];
int c = 0, cur = 0, cur_used = 0;
unsigned int id = 0;
while((c + 1) * w <= j && id < a.size()){
cur += a[id].ft;
c++;
dp[in][j] = max(dp[in][j], dp[in-1][j-c*w] + cur);
ans = max(ans, dp[in][j]);
cur_used++;
if(cur_used == a[id].se){
cur_used = 0;
id++;
}
}
}
in++;
}
cout << ans;
return 0;
}
