#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
#define endl '\n'
#define int long long
const long long mod = 998244353, Mxn = 505, INF = 1e18;
struct item{
int w, v, k;
friend bool operator<(const item &a, const item &b){
if(a.w != b.w){
return a.w > b.w;
}
return a.v > b.v;
}
friend istream &operator>>(istream &is, item &a){
is >> a.v >> a.w >> a.k;
return is;
}
friend ostream &operator<<(ostream &os,const item &a){
os << a.v << " " << a.w << " " << a.k;
return os;
}
};
template<typename T>
void smax(T &a, T b){
a = max(a, b);
}
void solve()
{
int n, W;
cin >> W >> n;
vector<item>v(n + 1);
for(int i = 1;i <= n;i++){
cin >> v[i];
}
sort(v.begin() + 1, v.end());
vector<vector<int>>dp(n + 2,vector<int>(W + 1));
for(int i = 1;i <= n;i++){
for(int j = 0;j <= W;j++){
int left = W - j;
item cur = v[i];
int take = min(cur.k, left / cur.w);
int weight = take * cur.w;
int cost = take * cur.v;
if(j + weight <= W){
smax(dp[i][j + weight], dp[i - 1][j] + cost);
}
smax(dp[i + 1][j], dp[i][j]);
}
}
int ans = *max_element(dp[n].begin(), dp[n].end());
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
FileRedirect("test");
#endif
// freopen("revegetate.in","r",stdin);
// freopen("revegetate.out","w",stdout);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
}
