#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MINF = -1e9 , MAXN = 2e3 + 10;
vector<pair<int,int>> vec[MAXN];
vector<int> dp(MAXN);
int main(){
int s , n , ans = 0;
cin >> s >> n;
for(int i = 1; i <= n; i++){
int v , w , c;
cin >> v >> w >> c;
vec[w].push_back({v , c});
}
for(int i = 1; i <= s; i++) dp[i] = MINF;
for(int i = 1; i <= s; i++){
sort(begin(vec[i]) , end(vec[i]));
int ma = s / i;
while(vec[i].size() > 0 and ma > 0){
auto [v , c] = vec[i].back();
vec[i].pop_back();
for(int j = s; j >= i; j--) dp[j] = max(dp[j - i] + v , dp[j]);
if(c - 1 > 0) vec[i].push_back({v , c - 1});
ma--;
}
ans = max(ans , dp[i]);
}
cout << ans;
}
