#include <iostream>
#include <vector>
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);
std::vector<long> v, w; int s, n; std::cin >> s >> n;
long counter = 0, t; int x, y, z;
for (int i=0; i < n; i++) {
std::cin >> y >> z >> x;
for (int j=0; j <= 30; j++) {
if (x == 0) break;
t = pow(2, j);
if (x < t) {
if (z*x <= s) {
v.push_back(y*x); w.push_back(z*x); counter++;
}
break;
} else {
if (z*t > s) break;
v.push_back(y*t); w.push_back(z*t); counter++; x -= t;
}
}
}
long arr[2][s+1];
for (long j=0; j <= s; j++) arr[0][j] = 0;
arr[1][0] = 0;
for (long i=1; i <= counter; i++) {
for (long j=1; j <= s; j++) {
if (j-w[i-1] >= 0) arr[i%2][j] = std::max(arr[(i-1)%2][j-w[i-1]]+v[i-1], arr[(i-1)%2][j]);
else arr[i%2][j] = arr[(i-1)%2][j];
}
}
std::cout << arr[counter%2][s] << '\n';
}
