#include <bits/stdc++.h>
using namespace std;
int s,n;
vector <pair <int,int>> temp[2009];
int cnt;
pair <int,int> knapsack[24009];
long long dp[2009];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
// freopen(".inp","r",stdin);
// freopen(".out","w",stdout);
cin >> s >> n;
for (int i = 1;i <= n;i++) {
int v,w,k;cin >> v >> w >> k;
temp[w].push_back({v,k});
}
for (int i = 1;i <= s;i++) {
vector <pair <int,int>>& curr = temp[i];
sort(curr.begin(),curr.end(),greater <pair <int,int>>());
int chosen = 0,lim = s/i;
for (auto x : curr) {
int ddd = min(lim - chosen,x.second);
chosen += ddd;
for (int t = 1;t <= ddd;t++) knapsack[++cnt] = {x.first,i};
if (chosen == lim) break;
}
}
for (int i = 1;i <= cnt;i++) {
for (int j = s;j >= knapsack[i].second;j--) {
dp[j] = max(dp[j],dp[j - knapsack[i].second] + knapsack[i].first);
}
}
cout << dp[s];
}
/*
Thuong em khi mua thu
Thuong em sang mua ha
Thuong em bang qua mua dong,gui gio xuan om em vao long
Thuong em bao mua mua
Tham thuong luon bao mua nang
Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/
