#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const int MAX = 1e5;
ll dp[2001][MAX]; // best V for each W using the first I types of items
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int S, N; cin >> S >> N;
for (int i = 0; i < N; ++i) {
int V, W; ll K;
cin >> V >> W >> K;
for (int pos = S; pos >= 0; --pos) {
int increment_pos = pos;
int items_used = 0;
ll add_weight = 0;
while (increment_pos <= S && items_used <= K) {
dp[increment_pos][i + 1] = max(dp[increment_pos][i + 1], dp[pos][i] + add_weight);
increment_pos += W;
++items_used;
add_weight += V;
}
}
}
ll ans = 0;
for (int i = 0; i <= S; ++i) {
ans = max(ans, dp[i][N]);
}
cout << ans << '\n';
}
