题目描述 Description
话说上回他给女孩送了n件礼物，由于是廉价的所以全部都坏掉了，女孩很在意这些礼物，所以决定自己缝补，但是人生苦短啊，女孩时间有限，她总共有m分钟能去缝补礼物。由于损坏程度不一样所以缝补的时间p也是不一样的，每件礼物呢，都有一个女孩的喜爱程度为w，后面还有一个数字h为这种礼物的件数。女孩想让自己的喜爱程度的和最大，那么请聪明的你帮她算一算！（注意：礼物非常多，不一定都能缝补完，女孩也不用把所有时间都花费）
输入描述 Input Description
第1行2个整数 m,n
第2行到第n+1行 每行三个整数 p，w，h
输出描述 Output Description
一个整数s表示最大的喜爱程度
样例输入 Sample Input
8 2
2 100 4
4 100 2
样例输出 Sample Output
400
数据范围及提示 Data Size & Hint
m<=10000
n<=100
p,h,w<=6000
#include<cstdio>
#include<iostream>
#define M 10010
#define N 110
using namespace std;
int s[N],v[N],w[M],f[M];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&w[i],&v[i],&s[i]);
for(int i=;i<=n;i++)
for(int j=m;j>=;j--)
for(int k=;k<=s[i];k++)
if(j>=k*w[i])
f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
printf("%d",f[m]);
return ;
}