#include <bits/stdc++.h>
using namespace std;
#define int long long
int limit, n;
map<int, vector<pair<int,int>>> mp;
void Solve()
{
// dp[i][j] tong lon nhat tao dc tu i tap weight dau tien voi weight <= j
vector<vector<int>> dp(mp.size()+5, vector<int>(limit+5, 0));
int i = 1, ans = 0;
dp[0][0] = 0;
for (map<int,vector<pair<int,int>>>::iterator it = mp.begin(); it != mp.end(); it++)
{
int w = it->first;
vector<pair<int,int>> vk = it->second;
sort(vk.begin(), vk.end(), greater<pair<int,int>>());
for (int m = 0; m <= limit; m++)
{
dp[i][m] = dp[i-1][m];
int copies = 0;
int cnt_vk = 0;
int cur_used = 0;
int profit = 0;
while ((copies+1) * w <= m && cnt_vk < vk.size())
{
copies++;
profit += vk[cnt_vk].first;
dp[i][m] = max(dp[i][m], dp[i-1][m-copies*w] + profit);
cur_used++;
if (cur_used == vk[cnt_vk].second){
cnt_vk++;
cur_used = 0;
}
}
ans = max(ans, dp[i][m]);
}
i++;
}
cout << ans;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> limit >> n;
for (int i = 1; i <= n; i++)
{
int v, w, k; cin >> v >> w >> k;
mp[w].push_back({v,k});
}
Solve();
return 0;
}
