A4383. 【算法】秒杀双十一
编程题
入门
知识点
题目描述
青青草原在今年也接入光纤，网络速度蹭蹭得上了好几级，Gold King有幸成为其中第一批用户。
Gold King能上网想到的第一件事就是秒杀双十一。于是他看了看购物车，整理了一下自己的物品，发现某些商品只需要买一件或者不买，有些商品需要越多越好，有些商品看商家给的限购额。Gold King对每种商品有一个重要度，试着帮Gold King计算一下在总费用M的情况，得到的重要度值最大。
Gold King能上网想到的第一件事就是秒杀双十一。于是他看了看购物车，整理了一下自己的物品，发现某些商品只需要买一件或者不买，有些商品需要越多越好，有些商品看商家给的限购额。Gold King对每种商品有一个重要度，试着帮Gold King计算一下在总费用M的情况，得到的重要度值最大。
输入格式
第一行输入两个整数M和N，表示总费用M和物品数量N。 接下来输入N行，每行输入P,C,X,表示每种商品的价格，重要度和最大购买数量，若X为0表示此物品可以购买无数个。
输出格式
输出一行最大重要度。
输入输出样例
输入 #1
10 3 2 1 0 3 3 1 4 5 4
输出 #1
11
说明/提示
5 <=M <=200
1 <=N <=30
1 <=P <=50
1 <=C <=80
0 <=X <=20
1 <=N <=30
1 <=P <=50
1 <=C <=80
0 <=X <=20