#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define AC ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
const ll mod = 998244353;
ll s , n;
vector<ll> v , w , k;
ll sub1()
{
ll res = min(k[0] ,(s/w[0] ) ) * v[0];
return res;
}
ll sub23()
{
vector<pair<ll,ll>> a;
for(ll i = 0 ; i<n ; i++)
{
for(ll j = 0 ; j<k[i] ; j++)
{
a.push_back({v[i] , k[i]});
}
}
vector<ll> dp(s+1 , 0);
for(pair<ll,ll> p: a)
{
for(ll i = s ; i>=p.second ; i--)
{
dp[i] = dp[i-1];
dp[i] = max(dp[i] , dp[i-p.second] + p.first);
}
}
return dp[s];
}
int main()
{
AC
cin>>s>>n;
v.resize(n);
w.resize(n);
k.resize(n);
for(ll i = 0 ; i<n ; i++)
{
cin>>v[i]>>w[i]>>k[i];
}
if(n == 1) cout<<sub1();
else cout<<sub23();
return 0;
}
