#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;
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("avx2")))
void up32(int v, int w, int l)
{
typedef int ymm __attribute((vector_size(32),aligned(4)));
for (int i = 2040; i >= l; i -= 8)
*(ymm*)(ans+i) = __builtin_ia32_pmaxsd256(*(ymm*)(ans+i), *(ymm*)(ans+i-w) + v);
}
void up(int v, int w)
{
int l = w%8?w+8-w%8:w;
up32(v, w, l);
LoopR (i,w,l)
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';
}
