#include <bits/stdc++.h>
#pragma GCC("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define ll long long
#define db double
#define vl vector<ll>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define BIT(x, i) (((x) >> (i)) & 1)
#define PROBLEM "test"
int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int mod[] = {(int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277, (int)1e9+ 9277};
const double eps = 1e-9;
const int LOG = 17;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
// ----------------------------------------
void solve() {
int n, m;
cin >> m >> n;
vector<int> w, v;
w.pb(0), v.pb(0);
for(int i = 1; i <= n; i++) {
int W, V, a;
cin >> V >> W>> a;
int pw = 1;
while(a >= pw) {
a -= pw;
w.pb(W * pw);
v.pb(V * pw);
pw <<= 1;
}
if(a > 0)
w.pb(W * a), v.pb(V * a);
}
int dp[m + 1];
memset(dp, 0, sizeof(dp));
n = w.size() - 1;
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
if(j >= w[i])
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[m] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(PROBLEM".inp", "r")){
freopen(PROBLEM".inp", "r", stdin);
freopen(PROBLEM".out", "w", stdout);
}
bool ok = false;
if(ok) {
int t; cin >> t;
while(t--) solve();
}
else
solve();
}
