#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2")
// #pragma GCC target("bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define endl '\n'
#define all(v) v.begin(), v.end()
#define print(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
#define mod 1000000007
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MAX = 200500;
int add(int a, int b){return (a+b)%mod;}
int sub(int a, int b){return (a-b+mod)%mod;}
int mul(int a, int b){return (1ll*a*b)%mod;}
void solve()
{
int s,n;
cin>>s>>n;
vector<ll> w,v;
for(int i=0;i<n;i++)
{
ll x,y,q;
cin>>x>>y>>q;
for(int i=0;i<=30;i++)
{
if((1<<i)<=q)
{
v.push_back((1<<i)*x);
w.push_back((1<<i)*y);
q-=(1<<i);
}
}
if(q) v.push_back(q*x), w.push_back(q*y);
}
vector<ll> dp(s+1,0);
for(int i=0;i<v.size();i++)
{
for(int j=s;j>=w[i];j--)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[s]<<endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int test=1;
//cin>>test;
while(test--)
{
solve();
}
exit(0);
}
