#include <bits/stdc++.h>
using namespace std;
#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define int uint32_t
#define pb push_back
#define fr first
#define sc second
#define __ << " " <<
const int N = 1e5 + 5;
const int S = 2e3 + 5;
int dp[N][S];
void solve () {
int n, s; cin >> s >> n;
int v[n], w[n], k[n];
for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s; j++) {
dp[i][j] = dp[i][j - 1];
int count = max(min(j / w[i - 1], k[i - 1]), (int) 0);
for (int ii = 0; ii <= count; ii++) {
int weight = ii * w[i - 1], value = ii * v[i - 1];
if (j - weight < 0) break;
dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value);
}
}
}
cout << dp[n][s] << endl;
}
/*
-- Sample 1 --
Input:
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1
Output:
15
-- Sample 2 --
Input:
20 3
5000 15 1
100 1 3
50 1 4
Output:
5400
*/
/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\oj.uz\NOI18\NOI18_knapsack.cpp" -o _run
*/
int32_t main () {
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
#ifdef LOCAL
clock_t __START__ = clock();
FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
#endif
solve();
#ifdef LOCAL
fclose(__FILE_IN__);
fclose(__FILE_OUT__);
cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
#endif
return 0;
}
