#include <iostream>
#include <vector>
#include <array>
#include <functional>
#include <cstdint>
using namespace std;
#define int int64_t
int32_t main() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> a(m);
for (int i = 0; i < m; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
}
vector<vector<int>> dp(m, vector<int>(n + 1, -1));
function<int(int, int)> f = [&](int j, int w) -> int {
if (j == m) return 0;
if (dp[j][w] != -1) return dp[j][w];
int answer = 0;
for (int k = 0; k <= a[j][2]; k++) {
int weightNeeded = k * a[j][1];
if (weightNeeded > w) break;
answer = max(answer, k * a[j][0] + f(j + 1, w - weightNeeded));
}
return dp[j][w] = answer;
};
cout << f(0, n) << '\n';
}
