#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int s, n;
cin >> s >> n;
vector<vector<pair<int, int>>> vals(s + 1);
for (int i = 0; i < n; ++i)
{
int v, w, k;
cin >> v >> w >> k;
vals[w].push_back({ v, k });
}
vector<pair<int, int>> items{};
for (int w = 1; w <= s; ++w)
{
sort(vals[w].begin(), vals[w].end());
int maxCnt = s / w;
while (!vals[w].empty() && maxCnt)
{
int addCnt = min(maxCnt, vals[w].back().second);
maxCnt -= addCnt;
items.insert(items.end(), addCnt, { vals[w].back().first, w });
vals[w].pop_back();
}
}
vector<int> dp(s + 1);
for (pair<int, int> item : items)
{
for (int w = s; w >= item.second; --w)
{
dp[w] = max(dp[w], dp[w - item.second] + item.first);
}
}
cout << dp[s] << '\n';
return 0;
}
