#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(a) a.begin(), a.end()
#define el '\n'
const int maxN = 505;
const int base = 311;
const int MOD = 1e9+7;
const int INF = 1e15;
const int NEG_INF = -1e15;
const int MAX_DAYS = 1000;
int n, m, k, q;
string S, T, SS[maxN];
// int dp[maxN][maxN];
vector<int> g[maxN];
void run_test() {
int S, n;
cin >> S >> n;
map<int, vector<pii>> by_weight;
for(int i = 1; i <= n; i++){
int val, wei, amt;
cin >> val >> wei >> amt;
by_weight[wei].push_back({val, amt});
}
vector<vector<int>> best(by_weight.size() + 1,
vector<int>(S + 1, 0));
best[0][0] = 0;
int at = 1;
for(auto[w, items] : by_weight){
sort(all(items), greater<pii>());
for(int i = 0; i <= S; i++){
best[at][i] = best[at-1][i];
int cnt = 0;
int item_at = 0;
int item_used = 0;
int val = 0;
while((cnt+1) * w <= i && item_at < items.size()){
cnt++;
val += items[item_at].fi;
best[at][i] = max(best[at][i], best[at-1][i - cnt*w] + val);
item_used++;
if(item_used == items[item_at].se){
item_at++;
item_used = 0;
}
}
}
at++;
}
cout << best.back()[S];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("snakes.in", "r", stdin);
// freopen("snakes.out", "w", stdout);
int test = 1;
// cin >> test;
while (test-- > 0)
{
run_test();
}
}
