#include <bits/stdc++.h>
using namespace std;
template<class T> using V = vector<T>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = V<int>;
using vll = V<ll>;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)((x).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i,n) for (int i = 1; i <= (int)(n); ++i)
#define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i)
#define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i)
const ll INF64 = (1LL<<62) - 1;
const int INF = 0x3f3f3f3f;
const int MOD = 1'000'000'007;
struct FastIO {
FastIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(std::ios::fixed); cout.precision(12);
}
} fastio;
inline void setIO(const string& inFile, const string& outFile){
if (!inFile.empty()) assert(freopen(inFile.c_str(), "r", stdin) != nullptr);
if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr);
}
inline void setIO(const string& base){
setIO(base + ".in", base + ".out");
}
template <class T, class U>
struct PairHash {
std::size_t operator()(const std::pair<T, U>& p) const noexcept {
std::size_t h1 = std::hash<T>{}(p.first);
std::size_t h2 = std::hash<U>{}(p.second);
return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
}
};
template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; }
template<class T> inline T ceil_div(T a, T b){
return (a>=0 ? (a + b - 1)/b : a/b);
}
template<class T> inline T floor_div(T a, T b){
return (a>=0 ? a/b : (a - b + 1)/b);
}
template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); }
template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); }
template<class T>
vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){
vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end());
if(values_out) *values_out = v;
vector<int> id(a.size());
rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin());
return id;
}
template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){
for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " ");
return os;
}
struct DSU {
V<int> e; void init(int N) { e = V<int>(N,-1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};
const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1};
const int kx[8] = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2};
int mod = 1000000007;
struct item{
long double avg;
int id, v, w, k;
bool operator<(item other){
return avg < other.avg || (avg == other.avg && w > other.w);
}
};
int main(){
int S, N;
cin >> S >> N;
V<item> v;
rep(i, N){
int V, W, K;
cin >> V >> W >> K;
v.pb({V/(long double)W, i, V, W, K});
//cout << "weight value " << i << " = value: " << V << ", weight " << W << ", copies " << K << endl;
}
//things are commutative, once you hit a weight, you don't need to go to it again, but if you haven't hit it, using all possible copies of current thing is the best move
vll dp(S+1, -1);
dp[0] = 0;
pii prev[S+1]{};
V<unordered_map<int, int>> c(S+1);
for(int i = 0; i <= S; i++){
if(dp[i] == -1) continue;
if(i){
c[i] = c[prev[i].first];
c[i][prev[i].second]++;
//cout << "i = " << i << ", copies array: " << vi(c[i], c[i]+N) << endl;
}
int cc[N]{};
for(auto [k, v]: c[i]){
cc[k] = v;
}
//cout << "max to weight " << i << " is derived from weight i = " << prev[i].first << " after adding weight value " << prev[i].second << endl;
for(auto [avg, id, value, weight, copies]: v){
if(i+weight <= S && cc[id] < copies && dp[i+weight] < dp[i]+value){
dp[i+weight] = dp[i]+value;
prev[i+weight] = {i, id};
}
}
//cout << i << endl;
//cout << dp << endl;
//cout << "after [" << avg << ", " << value << ", " << weight << ", " << copies << "], dp = " << dp << endl;
}
cout << *max_element(all(dp)) << endl;
}
//what if there's like a proportionally better but the worst thing is
