#include<stdio.h>
#include<iostream>
#define maxm 101
#define maxv 501
using namespace std;
int amount[maxm],size[maxm],value[maxm];
int v,m;
int i,j,k;
int f[maxm][maxv];
void init()
{
scanf("%d%d",&v,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&amount[i],&size[i],&value[i]);
}
void work()
{
for(i=1;i<=m;i++)
for(j=1;j<=v;j++)
for(k=0;k<=amount[i];k++)
if(j>=size[i]*k)
f[i][j]=max(f[i-1][j],f[i][j-size[i]*k]+value[i]*k);
else
f[i][j]=f[i-1][j];
printf("%d\n",f[m][v]);
}
int main()
{
init();
work();
system("pause");
return 0;
}
#include<iostream>
#define maxm 101
#define maxv 501
using namespace std;
int amount[maxm],size[maxm],value[maxm];
int v,m;
int i,j,k;
int f[maxm][maxv];
void init()
{
scanf("%d%d",&v,&m);
for(i=1;i<=m;i++)
scanf("%d%d%d",&amount[i],&size[i],&value[i]);
}
void work()
{
for(i=1;i<=m;i++)
for(j=1;j<=v;j++)
for(k=0;k<=amount[i];k++)
if(j>=size[i]*k)
f[i][j]=max(f[i-1][j],f[i][j-size[i]*k]+value[i]*k);
else
f[i][j]=f[i-1][j];
printf("%d\n",f[m][v]);
}
int main()
{
init();
work();
system("pause");
return 0;
}
