#include <bits/stdc++.h>
using namespace std;
bool check(map<int, map<int, int>>& dp, int n, int s)
{
if (dp.find(n) != dp.end())
{
if (dp[n].find(s) != dp[n].end())
return true;
return false;
}
return false;
}
int answer(map<int, map<int, int>>& dp, vector<int>& value, vector<int>& weight, vector<int>& copies, int s, int n)
{
if (copies[n] < 0 || s < 0)
return -1e9;
if(n < 0)
return 0;
if (n == 0)
{
int can_take = min(copies[n], s / weight[n]);
return dp[n][s] = can_take * value[n];
}
int best = answer(dp, value, weight, copies, s, n - 1); // Skip this item
for (int k = 1; k <= copies[n]; ++k) {
int total_weight = k * weight[n];
int total_value = k * value[n];
if (s >= total_weight) {
best = max(best, answer(dp, value, weight, copies, s - total_weight, n - 1) + total_value);
}
}
return dp[n][s] = best;
}
int main() {
long long int s, n;
cin >> s >> n;
vector<int> value;
vector<int> weight;
vector<int> copies;
int temp = n;
while (n--)
{
int vi, wi, ki;
cin >> vi >> wi >> ki;
value.push_back(vi);
weight.push_back(wi);
copies.push_back(ki);
}
map<int, map<int, int>> dp;
cout << answer(dp, value, weight, copies, s, temp - 1) << endl;
}
