#include<bits/stdc++.h>
using namespace std;
#define TASK "task"
const int mxN = 5e5 + 7;
const int inf = 1e9 + 67;
struct item {
int w , v , k;
}a[mxN];
int n;
int S;
long long dp[mxN];
void solve(void) {
cin >> S >> n;
for (int i = 1; i <= n; i++)
cin >> a[i].v >> a[i].w >> a[i].k;
memset(dp , -0x3f , sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
if(!a[i].w) {
for (int j = 0; j <= S; j++)
dp[j] += 1LL * a[i].v * a[i].k;
continue;
}
int c = 1;
while(a[i].k > 0) {
int can = min(c , a[i].k);
long long W = 1LL * can * a[i].w;
long long V = 1LL * can * a[i].v;
for (long long j = S; j >= W; j--)
dp[j] = max(dp[j] , dp[j - W] + V);
a[i].k -= can;
c *= 2;
}
}
long long ans = -inf;
for (int i = 0; i <= S; i++)
ans = max(ans , dp[i]);
cout << ans;
}
int main() {
ios_base :: sync_with_stdio(0);
cin.tie(0);
//freopen(TASK".inp","r",stdin);
//freopen(TASK".out","w",stdout);
int tc = 1;
//cin >> tc;
while(tc--) solve();
return 0;
}
