#include <bits/stdc++.h>
#define int long long
#define in insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
//#define mid (l+r)/2
#define all(v) v.begin(),v.end()
//#define pop pop_back
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int M=998244353;
int s,n,dp[2009],b[100009][3],dp2[2009],p[11];
bool vis[2009];
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
p[0]=1;
for(int i=1;i<=10;i++) p[i]=p[i-1]*10;
cin>>s>>n;
for(int i=1;i<=n;i++){
cin>>b[i][0]>>b[i][1]>>b[i][2];
for(int j=0;j<=s;j++) vis[j]=0;
for(int j=s;j>=0;j--){
if(vis[j]) break;
deque<pair<int,int>> q;
for(int k=0;k<=b[i][2];k++){
if(k*b[i][1]>j) break;
int val=dp[j-k*b[i][1]]+b[i][0]*k;
while(!q.empty()){
if(q.front().F<=val) q.pop_front();
else break;
}
q.push_front({val,j-b[i][1]*k});
}
vis[j]=1;
dp[j]=q.back().F;
for(int k=1;k<=2001;k++){
if(j-k*b[i][1]<0) break;
int cur=j-k*b[i][1];
vis[cur]=1;
if(q.back().S>cur) q.pop_back();
if(cur-b[i][2]*b[i][1]>=0){
int val=dp[cur-b[i][2]*b[i][1]]+b[i][0]*(b[i][2]+k);
while(!q.empty()){
if(q.front().F<=val) q.pop_front();
else break;
}
q.push_front({val,cur-b[i][2]*b[i][1]});
}
dp[cur]=q.back().F-k*b[i][0];
}
}
}
cout<<dp[s];
return 0;
}
