#include <iostream>
#include <algorithm>
using namespace std;
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int S, n;
struct tripla {
int val, weight, cnt;
};
tripla input[100001];
bool csort(tripla a, tripla b) {
if (a.val > b.val)
return 1;
return 0;
}
pair<int, int> a[100001];
int l;
int need[2001];
int dp[2][2001];
const int Inf = 2e9 + 1;
int main() {
fast
int i, j;
cin >> S >> n;
for (i = 1; i <= n; i++)
cin >> input[i].val >> input[i].weight >> input[i].cnt;
sort(input + 1, input + n + 1, csort);
for (i = 1; i <= S; i++)
need[i] = S / i;
for (i = 1; i <= n; i++) {
for (j = 1; j <= min(need[input[i].weight], input[i].cnt); j++)
a[++l] = {input[i].weight, input[i].val};
j--;
need[input[i].weight] -= j;
}
for (i = 0; i <= 1; i++)
for (j = 0; j <= S; j++)
dp[i][j] = -Inf;
dp[0][0] = dp[1][0] = 0;
for (i = 1; i <= l; i++)
for (j = 1; j <= S; j++)
if (j - a[i].first >= 0)
dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - a[i].first] + a[i].second);
else dp[i % 2][j] = dp[1 - i % 2][j];
int Max = 0;
for (i = 1; i <= S; i++)
if (dp[n % 2][i] > Max)
Max = dp[n % 2][i];
cout << Max;
return 0;
}
