#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
#include <unordered_map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <unordered_set>
#include <stack>
using namespace std;
struct Object {
int worth;
int weight;
int capacity;
bool operator<(const Object& other) const {
if (weight == other.weight) {
return worth < other.worth;
}
return weight < other.weight;
}
};
int main() {
int maxSum, nOfObjects;
cin >> maxSum >> nOfObjects;
vector<Object> objects(nOfObjects);
for (int i = 0; i < nOfObjects; ++i) {
cin >> objects[i].worth >> objects[i].weight >> objects[i].capacity;
}
std::sort(objects.begin(), objects.end());
vector<vector<int>> dp(nOfObjects+1, vector<int>(maxSum+1, 0));
for (int object = 1; object <= nOfObjects; ++object) {
for (int sum = 1; sum <= maxSum; ++sum) {
int usingOnlyThis = min(objects[object-1].capacity, sum/objects[object-1].weight) * objects[object-1].worth;
dp[object][sum] = usingOnlyThis;
for (int testSum = 1; testSum <= sum; ++testSum) {
usingOnlyThis = min(objects[object-1].capacity, (sum-testSum)/objects[object-1].weight) * objects[object-1].worth;
dp[object][sum] = max(dp[object][sum], dp[object-1][testSum] + usingOnlyThis);
}
}
}
cout << dp[nOfObjects][maxSum] << endl;
return 0;
}
