#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7; // 998244353
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int S, N;
cin >> S >> N;
vector<int> V(N), W(N), K(N);
set<int>DW;
vector<priority_queue<pair<int,int>>>maxW(S+1);
for (int i = 0; i < N; i++)
{
cin >> V[i] >> W[i] >> K[i];
DW.insert(W[i]);
maxW[W[i]].push({V[i],K[i]});
}
vector<int>cnt(S+1,0);
vector<vector<pair<int,int>>>BestW(S+1);
for (auto w:DW)
{
while (cnt[w]<S/w && !maxW[w].empty())
{
int curV=maxW[w].top().first,curK=maxW[w].top().second;
maxW[w].pop();
if(cnt[w]+curK<=S/w){
cnt[w]+=curK;
BestW[w].push_back({curV,curK});
}else{
BestW[w].push_back({curV,S/w - cnt[w]});
cnt[w]=S/w;
}
}
}
vector<int> dp(S + 1);
dp[0] = 0;
for (auto w:DW)
{
for (auto i:BestW[w])
{
int k=i.second,v=i.first;
for (int j = 0; j < k; j++)
{
for (int jj = S; jj >= w; jj--)
{
dp[jj]=max(dp[jj],dp[jj-w]+v);
}
}
}
}
cout << dp[S] << endl;
return 0;
}
