#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n, S, val[N], w[N], sl[N];
int dp[2005];
void sub1() {
cout << min(S / w[1], sl[1]) * val[1];
exit(0);
}
void sub23() {
memset(dp, -0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = sl[i]; j >= 1; --j) {
for(int k = S; k >= w[i]; --k) {
dp[k] = max(dp[k], dp[k - w[i]] + val[i]);
}
}
}
int ans = 0;
for(int i = 1; i <= S; ++i) ans = max(ans, dp[i]);
cout << ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> S >> n;
for(int i = 1; i <= n; ++i) {
cin >> val[i] >> w[i] >> sl[i];
}
if(n == 1) sub1();
bool s23 = 1; for(int i = 1; i <= n; ++i) if(sl[i] > 10) s23 = 0;
if(n <= 100 && s23) sub23();
return 0;
}
