#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define endl '\n'
const int MOD = 1e9+7;
const int inf =1e9;
bool multi=false;
int max_t=1000;
int f(int i, int s, vector<pair<int, int>> &a, vector<vector<int>> &dp) {
if (i==0) {
if (s>=a[i].second) return a[i].first;
else return 0;
}
if (dp[i][s]!=-1) return dp[i][s];
int take=a[i].first+f(i-1, s-a[i].second, a, dp);
int notake=f(i-1, s,a, dp);
return dp[i][s]=max(take, notake);
}
int main()
{
ll t=1;
if (multi) cin>>t;
while (t--) {
int s, n;
cin>>s>>n;
vector<vector<int>> a(n, vector<int>(3));
for (int i=0; i<n; i++) {
int v,w,k;
cin>>v>>w>>k;
a[i][0]=v;
a[i][1]=w;
a[i][2]=k;
}
vector<pair<int, int>> items;
for (auto i:a) {
int times=i[2];
for (int j=0; j<times; j++) {
items.push_back({i[0], i[1]});
}
}
vector<vector<int>> dp(items.size(), vector<int>(s+1, -1));
cout<<f(a.size()-1, s, items, dp);
}
return 0;
}
