/* {وَقُلْ رَبِّ زِدْنِي عِلْمًاً} */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mem(ARR, XX) memset(ARR,XX,sizeof ARR)
#define TY cin.tie(0), cout.tie(0),cin.sync_with_stdio(0), cout.sync_with_stdio(0);
int const N = 1e6 + 5;
ll dp[100][N];
int n,w;
struct item{ll w,v,k;};
item it[N];
ll slv(int i,ll W) {
if (i == n || !W)return 0;
ll &ret = dp[i][W];
if (~ret)return ret;
for (int j = 0; j <= it[i].k; ++j)
if (W - it[i].w * j >= 0)
ret = max(ret, slv(i + 1, W - it[i].w * j) + it[i].v * j);
return ret;
}
void jo() {
mem(dp, -1);
cin >> w >> n;
for (int i = 0; i < n; ++i)
cin >> it[i].v >> it[i].w >> it[i].k;
cout << slv(0, w);
}
int main() {
TY
jo();
}
