#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
const int LG=30;
int n, m, w[nx], v[nx], t[nx];
ll ans=0, dp[2005];
vector<pair<ll, int>> a;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>m>>n;
for(int i = 1; i <= n; i++)
cin>>v[i]>>w[i]>>t[i];
for(int i = 1; i <= n; i++)
{
t[i]=min(t[i], m/w[i]);
for(int j = 0; j <= LG; j++)
{
if(t[i]>=(1<<j))
{
t[i]-=(1<<j);
if(1ll*w[i]*(1<<j)<=m)
a.emplace_back(1ll*v[i]*(1<<j), w[i]*(1<<j));
}
}
if(t[i]>=0 && 1ll*w[i]*t[i]<=m)
a.emplace_back(1ll*v[i]*t[i], w[i]*t[i]);
}
for(auto it:a)
for(int i = m; i >= it.se; i--)
dp[i]=max(dp[i], dp[i-it.se]+it.fi);
cout<<*max_element(dp, dp+m+1);
}
