#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int mod = 1000000007, N = 2003, inf = 1000000007;
int dp[N];
struct node{
int v, w, k;
};
bool cnt(node a, node b){
return a.v * b.w * 1ll < a.w * b.v * 1ll;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("feast.in", "r", stdin);
// freopen("feast.out", "w", stdout);
for(int i = 0; i < N; ++i){
dp[i] = 0;
}
int s, n;
cin >> s >> n;
vector<node> v(n);
for(int i = 0; i < n; ++i){
cin >> v[i].v >> v[i].w >> v[i].k;
}
sort(v.begin(), v.end(), cnt);
// for(int i = 0; i < n; ++i) {
// cout << v[i].w << " ";
// }
for(int i = 0; i < n; ++i){
for(int j = s; j > 0; --j){
int cou = j / v[i].w;
cou = min(cou, v[i].k);
dp[j] = max(dp[j], dp[j - v[i].w * cou] + v[i].v * cou);
}
}
cout << dp[s];
}
