#include <iostream>
long ceil_log2(unsigned long long x) {
static const unsigned long long t[6] = {0xFFFFFFFF00000000ull, 0x00000000FFFF0000ull, 0x000000000000FF00ull, 0x00000000000000F0ull, 0x000000000000000Cull, 0x0000000000000002ull};
long y = (((x & (x - 1)) == 0) ? 0 : 1), j = 32;
for (long i = 0; i < 6; i++) {
long k = (((x & t[i]) == 0) ? 0 : j); y += k;
x >>= k; j >>= 1;
}
return y;
}
long pow(long x, long p) {
if (p == 0) return 1;
if (p == 1) return x;
long tmp = pow(x, p/2);
if (p%2 == 0) return tmp * tmp;
else return x * tmp * tmp;
}
int main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
long v[500000], w[500000]; long s, n; std::cin >> s >> n;
long counter = 0, x, t, y, z;
for (long i=0; i < n; i++) {
std::cin >> y >> z >> x;
for (long j=0; j <= 30; j++) {
if (x == 0) break;
t = pow(2, j);
if (x < t) {
v[counter] = y*x; w[counter] = z*x; counter++; break;
} else {
//std::cout << "hi!\n";
//std::cout << y << ' ' << z << ' ' << t << '\n';
v[counter] = y*t; w[counter] = z*t; counter++; x -= t;
//std::cout << counter-1 << ' ' << v[counter-1] << ' ' << w[counter-1] << '\n';
}
}
}
long arr[counter+1][s+1];
for (long i=1; i <= counter; i++) {
arr[i][0] = 0;
for (long j=0; j <= s; j++) {
arr[0][j] = 0;
if (j-w[i-1] >= 0) arr[i][j] = std::max(arr[i-1][j-w[i-1]]+v[i-1], arr[i-1][j]);
else arr[i][j] = arr[i-1][j];
}
}
/*
for (long i=0; i <= counter; i++) {
for (long j=1; j <= s; j++) {
std::cout << arr[i][j] << ' ';
}
std::cout << '\n';
}*/
std::cout << arr[counter][s] << '\n';
}
