#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
#define code signed main()
code
{
int n , m , mx = INT_MIN;
cin >> m >> n;
vec<int> a(n + 1) , b(n + 1) , c(n + 1) , dp(m + 1 , -1);
for (int i = 1; i <= n; i++)
cin >> b[i] >> a[i] >> c[i];
dp[0] = 0;
auto binsearch = [&](int i , int j){
int l = 1 , r = c[i] , ans = 1;
while(l <= r){
int mid = (l + r) >> 1;
if (j + a[i] * 1ll * mid <= m)
l = mid + 1 , ans = mid;
else r = mid - 1;
}
return ans;
};
for (int i = 1; i <= n; i++){
for (int j = m; j >= 0; j--){
int kol = binsearch(i , j);
if (dp[j] != -1 and j + a[i] * 1ll * kol <= m)
dp[j + a[i] * 1ll * kol] = max(dp[j + a[i] * 1ll * kol] , dp[j] + b[i] * 1ll * kol);
if (j + a[i] * 1ll * kol <= m)mx = max(dp[j + a[i] * 1ll * kol] , mx);
}
}
cout << (mx != -1 ? mx : 0) << "\n";
return 0;
}
