#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define str string
// pairs
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pd pair<ld, ld>
#define mp make_pair
#define f first
#define s second
// vectors
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rs resize
#define is insert
#define pb push_back
#define eb emplace_back
#define fr front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
// loops
#define FOR(n) for(int i=0; i<(n); ++i)
#define FOR1(a, b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x : a)
const int S=2e3;
ll s, n, v, w, k, dp[S+1];
void solve() {
cin >> s >> n;
if(n==1) {
cin >> v >> w >> k;
cout << v*min(s/w, k) << "\n";
} else {
FOR(n) {
cin >> v >> w >> k;
for(int j=0; j<k; ++j)
for(int l=s; l-w>=0; --l)
dp[l]=max(dp[l-w]+v, dp[l]);
}
cout << dp[s] << "\n";
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
