#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (auto i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()
#define int long long
#define double long double
const long long inf = (long long) 1e18;
const long long inf2 = LONG_LONG_MAX/2 - 100;
const long long mod = (int)1e9 + 7;
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int w, n; cin >> w >> n;
vector<vector<int>> v;
rep(i, 0, n){
int x, y, z; cin >> x >> y >> z;
int cur = 1;
while(cur <= z){
v.push_back({x*cur, y*cur, cur});
z -= cur;
}
if(z > 0) v.push_back({x*z, y*z, cur});
}
n = sz(v);
vector<int> dp(w+1, 0), prevdp(w+1, 0);
for(int i = 0; i < n; i++){
for(int j = 0; j <= w; j++){
if(i == 0){
if(j == v[i][1]) dp[j] = v[i][0];
}
else{
dp[j] = prevdp[j];
if(j >= v[i][1]) dp[j] = max(dp[j], prevdp[j-v[i][1]] + v[i][0]);
}
}
prevdp = dp;
dp.assign(w+1, 0);
}
int ans = *max_element(all(prevdp));
cout << ans << '\n';
}
