#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Item pair<ll, ll>
#define ItemList vector<Item>
const ll mod=998244353;
const ll MAX_CAP=2007;
const ll MAX_ITEMS=1e5+7;
ll values[MAX_ITEMS], weights[MAX_ITEMS], quantities[MAX_ITEMS];
void solve(){
ll S, N; cin>>S>>N;
ll max_quantity=0;
for (int i=0; i<N; i++) {
cin >> values[i] >> weights[i] >> quantities[i];
max_quantity = max(max_quantity, quantities[i]);
}
if (N==1) {
ll items_to_take = 0;
if (weights[0] > 0) {
items_to_take = std::min(S / weights[0], quantities[0]);
}
cout << values[0] * items_to_take << '\n';
} else if (N <= 100 && max_quantity <= 10) {
ll dp[MAX_CAP];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++) {
for (ll capacity = S; capacity >= weights[i]; capacity--) {
for (int count = 1; count <= quantities[i]; count++) {
if (capacity >= weights[i] * count) {
dp[capacity] = max(dp[capacity], dp[capacity - weights[i] * count] + values[i] * count);
}
}
}
}
cout << dp[S] << '\n';
} else {
ll dp[MAX_CAP];
memset(dp, 0, sizeof(dp));
ItemList items_by_weight[MAX_CAP];
for (int i = 0; i < N; i++) {
if (weights[i] < MAX_CAP) {
items_by_weight[weights[i]].push_back({values[i], quantities[i]});
}
}
for (int w = 1; w < MAX_CAP; w++) {
if (items_by_weight[w].empty()) continue;
sort(items_by_weight[w].rbegin(), items_by_weight[w].rend());
int current_item_idx = 0;
for (int i = 0; i < S / w; ++i) {
if (current_item_idx >= items_by_weight[w].size()) break;
ll current_value = items_by_weight[w][current_item_idx].first;
for (ll capacity = S; capacity >= w; capacity--) {
dp[capacity] = std::max(dp[capacity], dp[capacity - w] + current_value);
}
// "Use up" one item of this type and move to the next if needed.
items_by_weight[w][current_item_idx].second--;
if (items_by_weight[w][current_item_idx].second == 0) {
current_item_idx++;
}
}
}
std::cout << dp[S] << std::endl;
}
return;
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
// precomputation
//
const bool multitest=false;
if(multitest){
ll t; cin>>t;
while(t--){
solve();
}
} else {
solve();
}
return 0;
}
