#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll s, n;
ll value[100010], weight[100010], number[100010];
ll dp[2020];
int main()
{
cin>>s>>n;
for(int i=1; i<=n; i++)cin>>value[i]>>weight[i]>>number[i];
for(int i=1; i<=number[1] and i*weight[1]<=s; i++)dp[i*weight[1]]=value[1]*i;
for(int i=2; i<=n; i++)
{
for(int j=s; j>=weight[i]; j--)
{
int k=1;
while(k<=number[i] and k*weight[i]<=j)
{
if(dp[j-k*weight[i]]!=0)dp[j]=max(dp[j-k*weight[i]]+k*value[i], dp[j]);
if(dp[j-k*weight[i]]==0 and j==k*weight[i])dp[j]=max(dp[j-k*weight[i]]+k*value[i], dp[j]);
k++;
}
}
}
ll rez=0;
for(int i=1; i<=s; i++)rez=max(rez, dp[i]);
cout<<rez;
return 0;
}
