#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#define MAX(x, y) ((x)>(y)?(x):(y))
const int N = 100'010;
const int S = 2048;
pii a[N*30];
int ans[S];
int n, m;
int s;
__attribute__((optimize("O3,unroll-loops"),target("avx")))
void up(int v, int w)
{
LoopR (i,w,S)
ans[i] = MAX(ans[i], ans[i-w] + v);
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> s >> n;
Loop (i,0,n) {
int v, w, k;
cin >> v >> w >> k;
k = min(k, s/w);
while (k) {
a[m++] = {v, w};
if (k%2 == 0)
a[m++] = {v, w};
v *= 2;
w *= 2;
k = (k-1)/2;
}
}
Loop (i,0,m) {
auto [v, w] = a[i];
up(v, w);
}
int ans = 0;
Loop (i,0,s+1)
ans = max(ans, ::ans[i]);
cout << ans << '\n';
}
