#include<bits/stdc++.h>
using namespace std;
#define int long long
class Solution{
private:
int N, S, V[100001], W[100001], K[100001];
public:
void init(){
cin >> S >> N;
for (int i = 1; i <= N; i++){
cin >> V[i] >> W[i] >> K[i];
}
}
int Solve(){
vector<pair<int,int>>knapsack[2001];
for (int i = 1; i<=N; i++){
knapsack[W[i]].emplace_back(make_pair(V[i], K[i]));
}
for (int j = 1; j<=2000; j++){
sort(knapsack[j].rbegin(), knapsack[j].rend());
}
vector<vector<int>>dp(2002, vector<int>(2002, 0));
for (int weight = 1; weight <= 2000; weight++){
for (int total = 0; total<=2000; total++){
int full = 0;
int val = 0;
for (auto item : knapsack[weight]){
for (int j = 1; j <= (int)item.second; j++){
full += weight;
val += item.first;
if (full + total <= 2000){
dp[weight][total + full] = max(dp[weight][total + full], dp[weight - 1][total] + val);
}else{
break;
}
}
}
dp[weight][total] = max(dp[weight][total], dp[weight - 1][total]);
}
}
int ans = 0;
for (int i = 0 ; i<=S; i++){
ans = max(ans, dp[2000][i]);
}
return ans;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
Solution resenie;
resenie.init();
cout<<resenie.Solve();
return 0;
}
