/*=======================================
Build : LOCAL / Debug
Compiler : g++ -std=gnu++17
Note: read problem twice ฅ(^>⩊<^) ฅ
=======================================*/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#include "debug.hpp"
#else
#define debug(...) ((void)0)
#endif
#define sz(v) ((int)((v).size()))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using ll = int64_t;
using db = long double;
const int mxN = (int)2e5+5;
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1};
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;
template<typename T> int lwb(const vector<T>& a, const T& x){
return lower_bound(a.begin(), a.end(), x) - a.begin(); }
template<typename T> int upb(const vector<T>& a, const T& x){
return upper_bound(a.begin(), a.end(), x) - a.begin(); }
template<typename T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
struct Item {
int value;
int cost;
int stock;
};
int dp[2005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int s, n;
cin >> s >> n;
vector<Item> a(n);
for(int i = 0; i < n; ++i)
cin >> a[i].value >> a[i].cost >> a[i].stock;
memset(dp, 0, sizeof(dp));
for(auto [val, w, k]: a) {
if((int64_t)w*k >= s) for(int j = 0; j <= s; ++j) {
if(j + w > s) break;
ckmax(dp[j+w], dp[j] + val);
} else {
int x = 1;
vector<pair<int,int>> v;
while(k > x) {
v.emplace_back(x*w, x*val);
k -= x;
x *= 2;
}
v.emplace_back(k*w, k*val);
for(auto [nx, nv]: v)
for(int j = s; j >= 0; --j) {
if(j - nx < 0) break;
ckmax(dp[j], dp[j-nx]+nv);
}
}
}
cout << dp[s];
return 0;
}
