#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <functional>
#include <utility>
using namespace std;
#define ll long long
// int helper_right(vector<vector<int> >&ar, int val) {
// }
// void dfs(vector<vector<int>>&table, vector<vector<int>>&adj, vector<int>&vis, int u, int&cnt) {
// vis[u] = 1;
// cnt++;
// for(int i:table[u]) {
// for(int j:adj[i]) {
// if(!vis[j]) {
// dfs(table, adj, vis, j, cnt);
// }
// }
// }
// }
int hcf(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
long long findLCM(int a, int b) {
return ((long long)a * b) / hcf(a, b);
}
bool isPallindrome(string&s) {
int n = s.size();
int l = 0;
int r = n-1;
while(l < r) {
// cout<<s[l]<<" "<<s[r]<<"\n";
if(s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
void func() {
int s, n;
cin>>s>>n;
vector<array<int, 3> > ar(n);
for(int i=0;i<n;i++) {
cin>>ar[i][0]>>ar[i][1]>>ar[i][2];
}
vector<int> dp(s+1, -1);
dp[0] = 0;
for(int i=0;i<n;i++) {
vector<int> curr = dp;
for(int j=0;j<s && (j+ar[i][1]) <= s;j++) {
if(dp[j] != -1) {
for(int k=0;k<ar[i][2] && (j + ar[i][1]*(k+1)) <= s;k++) {
int ind = j + ar[i][1]*(k+1);
curr[ind] = max(curr[ind], dp[j] + ar[i][0] * (k+1));
}
}
}
dp = curr;
}
// cout<<"\n";
// for(int i=0;i<n;i++) {
// cout<<ar[i][0]<<" "<<ar[i][1]<<" "<<ar[i][2]<<"\n";
// }
int res = -1;
for(int i=0;i<=s;i++) res = max(res, dp[i]);
cout<<res<<"\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
std::cout.tie(0);
int t=1;
while(t--) {
func();
}
// func();
return 0;
}
