#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vb vector<bool>
#define vpii vector<pair<int, int>>
#define vpic vector<pair<int, char>>
#define vpis vector<pair<int, string>>
#define vvi vector<vector<int>>
#define pb push_back
#define pii pair<int, int>
#define vvpii vector<vector<pair<int, int>>>
#define rep(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()
#define fastio ios::sync_with_stdio(false); cin.tie(0);
#define MOD 1000000007
#define endl "\n"
signed main() {
fastio;
int s, n;
cin >> s >> n;
vi val(n), w(n), qty(n);
rep(i, 0, n) cin >> val[i] >> w[i] >> qty[i];
vi dp(s + 1);
rep(i, 0, n) {
int p = 1;
while(qty[i] > 0) {
int take = min(p, qty[i]);
int weight = take * w[i];
int value = take * val[i];
for (int j = s; j >= weight; j--) dp[j] = max(dp[j], dp[j - weight] + value);
qty[i] -= take;
p <<= 1;
}
}
cout << dp[s] << endl;
}
