#include <bits/stdc++.h>
using namespace std;
vector <vector <pair <int, int>>> arr(2001);
int n, W;
bool compare (pair <int, int> a, pair <int, int> b) {
return a.first > b.first; //value
}
int dp[2001][2001];
int ans (int pos, int weight) {
int &ret = dp[pos][weight];
if (ret != -1) return ret;
if (weight == 0 || pos == 0) return ret = 0;
int sum = 0;
int w = 0;
int pp = ans(pos - 1, weight);
for (auto i : arr[pos]) {
int val = i.first;
int amnt = i.second;
while (amnt--) {
sum += val;
w += pos;
if (w > weight) {
return ret = pp;
}
pp = max(pp, sum + ans(pos - 1, weight - w));
}
}
return ret = pp;
}
int main () {
memset (dp, -1, sizeof(dp));
cin >> W >> n;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
arr[b].push_back({a, c});
}
for (int i = 1; i <= 2000; i++) {
sort(arr[i].begin(), arr[i].end(), compare);
}
cout << ans(2000, W) << endl;
}
