#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
const int N = 2001;
ll dp[N];
vll cost[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int s, n; cin >> s >> n;
vector<pll> vec;
while(n--){
ll v, w; int a; cin >> v >> w >> a;
for(int i = 0; i <= 30; ++i){
if(a >= (1 << i)){
a -= (1 << i);
if(w * (1 << i) <= s)
cost[w * (1 << i)].push_back(v * (1 << i));
}
else{
if(w * a <= s) cost[w * a].push_back(v * a);
break;
}
}
}
memset(dp, -1, sizeof dp);
dp[0] = 0;
for(int v = 1; v <= s; ++v){
int lim = s / v;
sort(all(cost[v]), greater<ll>());
int sz = min(lim, (int)cost[v].size());
for(int i = 0; i < sz; ++i){
ll val = cost[v][i];
for(int j = s; j >= v; --j)
if(dp[j - v] != -1)
dp[j] = max(dp[j], dp[j - v] + val);
}
}
cout << *max_element(dp, dp + s + 1);
return 0;
}
