#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
struct P{
ll x, y;
};
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
signed main(){
fastio;
int s, n;
cin >> s >> n;
vector<tuple<int, int, int>> parr;
for (int i=0; i<n; i++){
int v, w, k;
cin >> v >> w >> k;
parr.push_back({w, v, k});
}
sort(rall(parr));
vector<int> value;
vector<int> price;
int cur=0;
int cnt=0;
for (auto [w, v, k]: parr){
if (w != cur) cur = w, cnt = 0;
int limit = (s-cnt*w)/w;
for (int i=0; i<min(limit, k); i++){
value.push_back(v);
price.push_back(w);
cnt++;
}
}
vector<int> dp (s+1);
n = value.size();
for (int i=0; i<n; i++){
for (int j=s; j-price[i]>=0; j--){
dp[j] = max(dp[j], dp[j-price[i]]+value[i]);
}
}
cout << dp[s] << '\n';
}
