#include <iostream>
#include <vector>
using namespace std;
int main()
{
int s, n; cin >> s >> n;
vector<vector<long long>> store(n, vector<long long>(3));
for(int i = 0; i < n; i++)
{
cin >> store[i][0] >> store[i][1];
long long temp; cin >> temp;
store[i][2] = min(s / store[i][1], temp);
}
vector<long long> dp(s + 1, 0);
for(int i = 0; i < n; i++)
{
for(int j = s; j >= store[i][1]; j--) dp[j] = max(dp[j - store[i][1]] + store[i][0], dp[j]);
store[i][2]--;
}
for(int i = 0; i < n; i++)
{
while(store[i][2] > 0)
{
if(dp[s - store[i][1]] + store[i][0] > dp[s])
{
for(int j = s; j >= store[i][1]; j--) dp[j] = max(dp[j - store[i][1]] + store[i][0], dp[j]);
store[i][2]--;
}
else store[i][2] = -1;
}
}
cout << dp[s] << endl;
}
