#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mo = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e15;
const int N = 2e5 + 10;
int M = 1e3 + 10;
#define int long long
ll binExp(ll a, ll b , ll mo) {
ll ans = 1;
a %= mo;
while (b) {
if (b & 1) ans = ans * a % mo;
a = a * a % mo;
b >>= 1;
}
return ans;
}
vector<vector<int>> div1(N);
void sieve(){
for (int i = 1; i < N ; ++i)
{
for(int j = i ; j < N ; j+=i){
div1[j].push_back(i);
}
}
}
int ad(int a , int b){
return (a+b)%mo;
}
int mul(int a ,int b){
return (a*b)%mo;
}
void solve() {
int n,s;
cin>>s>>n;
map<int,vector<pair<int,int>>> m;
for(int i = 0 ;i < n ; i++){
int v,w,k;
cin>>v>>w>>k;
m[w].push_back({v,k});
}
vector<vector<int>> dp(m.size()+1 , vector<int> (s+1 , -INF));
dp[0][0] = 0;
int at = 1;
for(auto &[w , item]: m){
sort(item.rbegin() , item.rend());
for(int i = 0 ; i <= s; i++){
dp[at][i] = dp[at-1][i];
int co = 0 , curr_used = 0 , profit = 0 , j = 0;
while((co+1)*w <= i && j < item.size()){
co++;
profit += item[j].first;
dp[at][i] = max(dp[at][i] , dp[at-1][i-co*w]+profit);
curr_used++;
if(curr_used == item[j].second){
curr_used = 0;
j++;
}
}
}
at++;
}
int g = m.size();
int ans = *max_element(dp[g].begin()+1 , dp[g].end());
cout<<ans<<endl;
}
signed main() {
// freopen("revegetate.in", "r", stdin);
// freopen("revegetate.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
// sieve();
// help();
while (t--) {
solve();
}
return 0;
}
