#include <cstdio>
#include <deque>
#include <utility>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> ii;
int s,n,v,w,k,it,e;
int arr[2005];
deque<ii> d;
void print(){
for (int x=0;x<=s;x++){
printf("%d ",arr[x]);
}
printf("\n");
}
inline int read() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x;
}
int main(){
//freopen("input.txt","r",stdin);
memset(arr,-1,sizeof(arr));
arr[0]=0;
s=read(),n=read();
for (int x=0;x<n;x++){
v=read(),w=read(),k=read();
for (int y=min(w-1,s-w);y>=0;y--){
d.clear();
it=y;
for (int z=0;it<=s;z++){
if (arr[it]!=-1){
e=arr[it]-v*z;
while (!d.empty() && d.back().first<=e) d.pop_back();
d.push_back(ii(e,z));
}
if (!d.empty()){
arr[it]=d.front().first+v*z;
if (d.front().second<=z-k)d.pop_front();
}
it+=w;
}
}
//print();
}
k=0;
for (int x=0;x<=s;x++){
k=max(k,arr[x]);
}
printf("%d\n",k);
}
