#include <bits/stdc++.h>
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MAX = 1e6+7;
const ll MOD = 1e9+7;
ll n,M;
struct trip {
ll w,v,a;
};
vector <trip> vec;
void solve() {
cin >> M >> n;
for(ll i=1; i<=n; ++i) {
ll w,v,a;
cin >> v >> w >> a;
a = min(a, M/w + 1);
ll pw = 1;
while(a > 0) {
ll take = min(pw,a);
if(w*take <= M)
vec.pb({w*take, v*take, 1});
a -= take;
pw *=2;
}
}
vector <ll> dp(M+1, 0);
for(auto j:vec) {
// cout << j.w << " " << j.v << " " << j.a << "\n";
for(ll i=M; i>=j.w; --i)
dp[i] = max(dp[i - j.w] + j.v, dp[i]);
}
cout << dp[M];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//if(fopen("TASK.INP","r")) {
// freopen("TASK.INP","r",stdin);
// freopen("TASK.OUT","w",stdout);
//}
solve();
cerr << "\n" << "Time elapsed: " << TIME << "s\n";
return 0;
}
