#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define int long long
#define AC ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long ll;
typedef unsigned long long ull;
ll max(ll a, ll b) { return (a > b) ? a : b; }
ll min(ll a, ll b) { return (a < b) ? a : b; }
ll gcd(ll a, ll b) { return __gcd(abs(a), abs(b)); }
ll lcm(ll a, ll b) { return abs(a) / gcd(a, b) * abs(b); }
ll LASTBIT(ll mask) { return mask & -mask; }
int pop_cnt(ull mask) { return __builtin_popcountll(mask); }
int ctz(ull mask) { return __builtin_ctzll(mask); }
int logOf(ull mask) { return 63 - __builtin_clzll(mask); }
template <class T1, class T2>
bool maximize(T1 &a, T2 b) {
if (a < b) { a = b; return true; }
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b) {
if (a > b) { a = b; return true; }
return false;
}
template <class T>
void printArr(const T &container, string sep = " ", string finish = "\n", ostream &out = cout) {
for (auto &it : container) out << it << sep;
out << finish;
}
struct item{
int v,w,k;
};
void solve() {
int s, n; cin >> s >> n;
vector<item> a(n);
for(int i = 0; i < n; i ++) cin >> a[i].v >> a[i].w >> a[i].k;
vector<int> dp(s+1, 0);
dp[0] = 1;
for(int i = 0; i < n; i ++){
int cnt = 1;
int v = a[i].v, w = a[i].w, k = a[i].k;
while(k > 0){
int x = min(cnt,k);
for(int j = s; j >= w; j--) dp[j] = max(dp[j],dp[j-(w*x)] + v*x);
k -= x;
cnt <<= 1;
}
}
cout << dp[s] << '\n';
}
signed main() {
AC
int t = 1;
clock_t start = clock();
// cin >> t;
for (int test = 1; test <= t; ++test) {
solve();
}
cerr << "Time: " << clock() - start << "ms **" << endl;
return 0;
}
