#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
const ll mod = 1e9 + 7;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
map<int,vvl>vals;
int main()
{
int s,n;
cin>>s>>n;
vvl a(n,vl(3));
for (int i = 0;i<n;i++){cin>>a[i][0]>>a[i][1]>>a[i][2];vals[a[i][1]].push_back(a[i]);}
if (n == 1){
int weight = a[0][1],worth = a[0][0],copies = a[0][2];
int num = s / weight;
num = min(num,copies);
cout<<worth * num;
return 0;
}
vvl sack;
for (int w = 1;w<=s;w++){
vvl cur = vals[w];
sort(cur.rbegin(),cur.rend());
int num = s/w;
int i = 0;
while (i<(int)cur.size() && num > 0){
num--;
sack.push_back({cur[i][0],w});
cur[i][2]--;
if (cur[i][2] == 0)i++;
}
}
n = (int)sack.size();
vvl dp(n,vl(s + 1));
for (int i = 0;i<n;i++){
for (int j = 1;j<=s;j++){
if (i != 0)dp[i][j] = dp[i - 1][j];
if (j < sack[i][1])continue;
int extra = (i == 0 ? 0 : dp[i - 1][j - sack[i][1]]);
dp[i][j] = max(dp[i][j],sack[i][0] + extra);
}
}
cout<<dp[n - 1][s];
return 0;
}
