#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define inf (ll)1000000007
#define llmax LLONG_MAX
#define pi 3.141592653589793238462643383279502884197169399
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
ll ncr(int n, int r)
{
if (n < r) return 0;
long long p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0) {
while (r) {
p *= n;
k *= r;
long long m = __gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
vector <ll> vcreate(int n){
vector <ll> v(n);
for (int i = 0; i < n; i++)
{
cin>>v[i];
}
return v;
}
const int MOD=998244353;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
ll ModExp(ll x, ll n, ll m) {
assert(n >= 0);
x %= m; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % m; }
x = x * x % m;
n /= 2;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("snakes.in", "r", stdin);
//freopen("snakes.out", "w", stdout);
/* ll T;
cin>>T;
for(ll oo=0; oo<T; oo++)
{
} */
int s{},n{};
cin>>s>>n;
vector<pair<int,pair<int,int>>> v(n);
for(int i{0}; i<n; i++)
{
cin>>v[i].first>>v[i].second.first>>v[i].second.second;
}
sort(all(v));
reverse(all(v));
vector<pair<int,int>> ac;
map<int,int> m;
for(int i{0}; i<n; i++)
{
for(int j{0}; j<v[i].second.second; j++)
{
if(m[v[i].second.first]>=s/v[i].second.first)break;
ac.push_back({v[i].first,v[i].second.first});
m[v[i].second.first]++;
}
}
vector<vector<ll>> dp(ac.size()+1,vll(s+1,0));
for(int i{0}; i<ac.size(); i++)
{
for(int j{0}; j<s; j++)
{
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
if(j+ac[i].second<=s)
{
dp[i+1][j+ac[i].second]=max(dp[i+1][j+ac[i].second],dp[i][j]+ac[i].first);
}
}
}
ll ans{0};
for(int i{0}; i<=s; i++)
{
ans=max(ans,dp[n][i]);
}
cout<<ans<<endl;
}
