/// PhongDang Cs4_uet
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define pii pair<int, int>
#define mx(x, y) max(x, y)
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define pob pop_back
#define all(x) x.begin(),x.end()
#define vii vector<int>
#define int long long
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) (1 << j) ^ i
#define onbit(i, j) (1 << j) i
#define built(mask) __builtin_popcountll(mask)
#define len(s) (int)((s).size())
#define iii pair<int,pair<int, int> >
#define fillcharval(a) memset(a, -0x3f, sizeof(a));
#define fillchar(a,x) memset(a, x, sizeof (a))
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return 1;} return 0;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
const int N = 1e6 + 6;
const int mod = 1e9 + 7;
const int base = 31;
const int inf = 1e9;
void add(ll &x, const ll y){
x+= y;
if(x>=mod) x-= mod;
}
int S, n;
struct task{
int val, wei, cnt;
}a[N];
namespace sub1{
bool checksub(void){
return (n == 1);
}
void sol(){
int can = S/a[1].wei;
can = min(can, a[1].cnt);
cout << can*a[1].val;
}
}
namespace sub23{
bool checksub(void){
// fo(i, 1, n) if(a[i].cnt > 10) return 0;
return (n <= 100);
}
int dp[2002];
void sol(){
fo(i, 1, n){
foi(j, S, a[i].wei){
int maxk = j/a[i].wei;
minimize(maxk, a[i].cnt);
fo(k, 0, maxk) maximize(dp[j], dp[j - a[i].wei*k] + a[i].val*k);
}
}
cout << dp[S];
}
}
namespace sub4{
int dp[2002];
vector<pii> items[2001];
vector<int> v;
int sz[N];
bool ok[N];
bool cmp(pii a, pii b){
return a.fi > b.fi;
}
void sol(){
dp[0] = 0;
fo(i, 1, S) dp[i] = 0;
fo(i, 1, n){
items[a[i].wei].pb({a[i].val, a[i].cnt});
sz[a[i].wei] += a[i].cnt;
if(!ok[a[i].wei]){
ok[a[i].wei] = 1;
v.push_back(a[i].wei);
}
}
for(auto it:v) sort(all(items[it]), cmp);
for(auto it:v){
// cout << it << "\n";
foi(j, S, it){
int maxk = j/it;
minimize(maxk, sz[it]);
// cout << j << " " << maxk << "\n";
int pos = 0;
int numitems = 0;
int sumval = 0;
fo(k, 1, maxk){
if(k > numitems + items[it][pos].se && pos < items[it].size() - 1){
numitems += items[it][pos].se;
pos++;
}
sumval += items[it][pos].fi;
// cout << k << " " << sumval << " " << pos << " " << dp[j - k*it]<< "\n";
maximize(dp[j], dp[j - k*it] + sumval);
// cout << dp[j - k*it] << " ";
}
}
}
cout << dp[S];
}
}
signed main()
{
faster
// in("task.inp");
// out("task.out");
// out("task.ans");
cin >> S >> n;
fo(i, 1, n) cin >> a[i].val >> a[i].wei >> a[i].cnt;
if(sub1::checksub()) return sub1::sol(), 0;
if(sub23::checksub()) return sub23::sol(), 0;
sub4::sol();
return 0;
}
