#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 main()
{
ll t=1;
if (multi) cin>>t;
while (t--) {
int s, n;
cin>>s>>n;
vector<pair<int, int>> items;
for (int i=0; i<n; i++) {
int v,w,k;
cin>>v>>w>>k;
for (int p=1; k>0; p<<=1) {
int cnt = min(p, k);
items.push_back({v*cnt, w*cnt});
k-=cnt;
}
}
vector<int> prev(s+1, 0), curr(s+1, 0);
for (int i=0; i<=s; i++) {
if (i>=items[0].second) prev[i]=items[0].first;
}
for (int i=1; i<items.size(); i++) {
for (int j=0; j<=s; j++) {
int take=0;
if (j>=items[i].second) take=items[i].first+prev[j-items[i].second];
int notake=prev[j];
curr[j]=max(take, notake);
}
swap(prev, curr);
}
cout<<prev[s];
}
return 0;
}
